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 while let Some(item) = pos.right.get() {
270 if item.deleted() {
271 pos.forward();
272 continue;
273 }
274
275 if let Content::Format { key, value } = &item.content {
276 let attr = attrs.get(key.as_str()).cloned().unwrap_or(Any::Null);
277 if attr == *value {
278 pos.forward();
279 continue;
280 }
281 }
282
283 break;
284 }
285}
286
287fn insert_item(store: &mut DocStore, ty: &mut YType, pos: &mut TextPosition, content: Content) -> JwstCodecResult {
288 if let Some(markers) = &ty.markers
289 && content.countable()
290 {
291 markers.update_marker_changes(pos.index, content.clock_len() as i64);
292 }
293
294 let item = store.create_item(
295 content,
296 pos.left.clone(),
297 pos.right.clone(),
298 Some(Parent::Type(pos.parent.clone())),
299 None,
300 );
301 let item_ref = item.clone();
302 store.integrate(Node::Item(item), 0, Some(ty))?;
303 pos.right = item_ref;
304 pos.forward();
305
306 Ok(())
307}
308
309fn insert_attributes(
310 store: &mut DocStore,
311 ty: &mut YType,
312 pos: &mut TextPosition,
313 attrs: &TextAttributes,
314) -> JwstCodecResult<TextAttributes> {
315 let mut negated = TextAttributes::new();
316
317 for (key, value) in attrs {
318 let current = pos.attrs.get(key.as_str()).cloned().unwrap_or(Any::Null);
319 if current == *value {
320 continue;
321 }
322
323 negated.insert(key.to_string(), current);
324 insert_item(
325 store,
326 ty,
327 pos,
328 Content::Format {
329 key: key.to_string(),
330 value: value.clone(),
331 },
332 )?;
333 }
334
335 Ok(negated)
336}
337
338fn insert_negated_attributes(
339 store: &mut DocStore,
340 ty: &mut YType,
341 pos: &mut TextPosition,
342 mut negated: TextAttributes,
343) -> JwstCodecResult {
344 while let Some(item) = pos.right.get() {
345 if item.deleted() {
346 pos.forward();
347 continue;
348 }
349
350 if let Content::Format { key, value } = &item.content
351 && let Some(negated_value) = negated.get(key.as_str())
352 && negated_value == value
353 {
354 negated.remove(key.as_str());
355 pos.forward();
356 continue;
357 }
358
359 break;
360 }
361
362 for (key, value) in negated {
363 insert_item(
364 store,
365 ty,
366 pos,
367 Content::Format {
368 key: key.to_string(),
369 value,
370 },
371 )?;
372 }
373
374 Ok(())
375}
376
377fn insert_text_content(
378 store: &mut DocStore,
379 ty: &mut YType,
380 pos: &mut TextPosition,
381 content: Content,
382 mut attrs: TextAttributes,
383) -> JwstCodecResult {
384 for key in pos.attrs.keys() {
385 if !attrs.contains_key(key.as_str()) {
386 attrs.insert(key.to_string(), Any::Null);
387 }
388 }
389
390 minimize_attribute_changes(pos, &attrs);
391 let negated = insert_attributes(store, ty, pos, &attrs)?;
392 insert_item(store, ty, pos, content)?;
393 insert_negated_attributes(store, ty, pos, negated)?;
394
395 Ok(())
396}
397
398fn format_text(
399 store: &mut DocStore,
400 ty: &mut YType,
401 pos: &mut TextPosition,
402 mut remaining: u64,
403 attrs: TextAttributes,
404) -> JwstCodecResult {
405 if remaining == 0 {
406 return Ok(());
407 }
408
409 minimize_attribute_changes(pos, &attrs);
410 let mut negated = insert_attributes(store, ty, pos, &attrs)?;
411
412 while remaining > 0 {
413 let Some(item) = pos.right.get() else {
414 break;
415 };
416
417 if item.deleted() {
418 pos.forward();
419 continue;
420 }
421
422 match &item.content {
423 Content::Format { key, value } => {
424 if let Some(attr) = attrs.get(key.as_str()) {
425 if attr == value {
426 negated.remove(key.as_str());
427 } else {
428 negated.insert(key.to_string(), value.clone());
429 }
430 store.delete_item(item, Some(ty));
431 pos.forward();
432 } else {
433 pos.forward();
434 }
435 }
436 _ => {
437 let item_len = item.len();
438 if remaining < item_len {
439 store.split_node(item.id, remaining)?;
440 remaining = 0;
441 } else {
442 remaining -= item_len;
443 }
444 pos.forward();
445 }
446 }
447 }
448
449 insert_negated_attributes(store, ty, pos, negated)?;
450
451 Ok(())
452}
453
454fn delete_text(store: &mut DocStore, ty: &mut YType, pos: &mut TextPosition, mut remaining: u64) -> JwstCodecResult {
455 if remaining == 0 {
456 return Ok(());
457 }
458
459 let start = remaining;
460
461 while remaining > 0 {
462 let item_ref = pos.right.clone();
463 let Some((indexable, item_len, item_id)) = item_ref.get().map(|item| (item.indexable(), item.len(), item.id))
464 else {
465 break;
466 };
467
468 if indexable {
469 if remaining < item_len {
470 store.split_node(item_id, remaining)?;
471 remaining = 0;
472 } else {
473 remaining -= item_len;
474 }
475
476 if let Some(item) = item_ref.get() {
477 store.delete_item(item, Some(ty));
478 }
479 }
480
481 pos.forward();
482 }
483
484 if let Some(markers) = &ty.markers {
485 markers.update_marker_changes(pos.index, -((start - remaining) as i64));
486 }
487
488 Ok(())
489}
490
491#[cfg(test)]
492mod tests {
493 use rand::{Rng, SeedableRng};
494 use rand_chacha::ChaCha20Rng;
495 use yrs::{Options, Text, Transact};
496
497 use super::{TextAttributes, TextDeltaOp, TextInsert};
498 #[cfg(not(loom))]
499 use crate::sync::{Arc, AtomicUsize, Ordering};
500 use crate::{Any, Doc, loom_model, sync::thread};
501
502 #[test]
503 fn test_manipulate_text() {
504 loom_model!({
505 let doc = Doc::new();
506 let mut text = doc.create_text().unwrap();
507
508 text.insert(0, "llo").unwrap();
509 text.insert(0, "he").unwrap();
510 text.insert(5, " world").unwrap();
511 text.insert(6, "great ").unwrap();
512 text.insert(17, '!').unwrap();
513
514 assert_eq!(text.to_string(), "hello great world!");
515 assert_eq!(text.len(), 18);
516
517 text.remove(4, 4).unwrap();
518 assert_eq!(text.to_string(), "helleat world!");
519 assert_eq!(text.len(), 14);
520 });
521 }
522
523 #[test]
524 #[cfg(not(loom))]
525 fn test_parallel_insert_text() {
526 let seed = rand::rng().random();
527 let rand = ChaCha20Rng::seed_from_u64(seed);
528 let mut handles = Vec::new();
529
530 let doc = Doc::with_client(1);
531 let mut text = doc.get_or_create_text("test").unwrap();
532 text.insert(0, "This is a string with length 32.").unwrap();
533
534 let added_len = Arc::new(AtomicUsize::new(32));
535
536 {
538 for i in 0..2 {
539 let mut text = text.clone();
540 let mut rand = rand.clone();
541 let len = added_len.clone();
542
543 handles.push(thread::spawn(move || {
544 for j in 0..10 {
545 let pos = rand.random_range(0..text.len());
546 let string = format!("hello {}", i * j);
547
548 text.insert(pos, &string).unwrap();
549
550 len.fetch_add(string.len(), Ordering::SeqCst);
551 }
552 }));
553 }
554 }
555
556 {
558 for i in 0..2 {
559 let doc = doc.clone();
560 let mut rand = rand.clone();
561 let len = added_len.clone();
562
563 handles.push(thread::spawn(move || {
564 let mut text = doc.get_or_create_text("test").unwrap();
565 for j in 0..10 {
566 let pos = rand.random_range(0..text.len());
567 let string = format!("hello doc{}", i * j);
568
569 text.insert(pos, &string).unwrap();
570
571 len.fetch_add(string.len(), Ordering::SeqCst);
572 }
573 }));
574 }
575 }
576
577 for handle in handles {
578 handle.join().unwrap();
579 }
580
581 assert_eq!(text.to_string().len(), added_len.load(Ordering::SeqCst));
582 assert_eq!(text.len(), added_len.load(Ordering::SeqCst) as u64);
583 }
584
585 #[cfg(not(loom))]
586 fn parallel_ins_del_text(seed: u64, thread: i32, iteration: i32) {
587 let doc = Doc::with_client(1);
588 let rand = ChaCha20Rng::seed_from_u64(seed);
589 let mut text = doc.get_or_create_text("test").unwrap();
590 text.insert(0, "This is a string with length 32.").unwrap();
591
592 let mut handles = Vec::new();
593 let len = Arc::new(AtomicUsize::new(32));
594
595 for i in 0..thread {
596 let len = len.clone();
597 let mut rand = rand.clone();
598 let text = text.clone();
599 handles.push(thread::spawn(move || {
600 for j in 0..iteration {
601 let len = len.clone();
602 let mut text = text.clone();
603 let ins = i % 2 == 0;
604 let pos = rand.random_range(0..16);
605
606 if ins {
607 let str = format!("hello {}", i * j);
608 text.insert(pos, &str).unwrap();
609
610 len.fetch_add(str.len(), Ordering::SeqCst);
611 } else {
612 text.remove(pos, 6).unwrap();
613
614 len.fetch_sub(6, Ordering::SeqCst);
615 }
616 }
617 }));
618 }
619
620 for handle in handles {
621 handle.join().unwrap();
622 }
623
624 assert_eq!(text.to_string().len(), len.load(Ordering::SeqCst));
625 assert_eq!(text.len(), len.load(Ordering::SeqCst) as u64);
626 }
627
628 #[test]
629 #[cfg(not(loom))]
630 fn test_parallel_ins_del_text() {
631 parallel_ins_del_text(973078538, 2, 2);
634 parallel_ins_del_text(18414938500869652479, 2, 2);
635 }
636
637 #[test]
638 fn loom_parallel_ins_del_text() {
639 let seed = rand::rng().random();
640 let mut rand = ChaCha20Rng::seed_from_u64(seed);
641 let ranges = (0..20).map(|_| rand.random_range(0..16)).collect::<Vec<_>>();
642
643 loom_model!({
644 let doc = Doc::new();
645 let mut text = doc.get_or_create_text("test").unwrap();
646 text.insert(0, "This is a string with length 32.").unwrap();
647
648 let handles = (0..2)
650 .map(|i| {
651 let text = text.clone();
652 let ranges = ranges.clone();
653 thread::spawn(move || {
654 let mut text = text.clone();
655 let ins = i % 2 == 0;
656 let pos = ranges[i];
657
658 if ins {
659 let str = format!("hello {}", i);
660 text.insert(pos, &str).unwrap();
661 } else {
662 text.remove(pos, 6).unwrap();
663 }
664 })
665 })
666 .collect::<Vec<_>>();
667
668 for handle in handles {
669 handle.join().unwrap();
670 }
671 });
672 }
673
674 #[test]
675 #[cfg_attr(miri, ignore)]
676 fn test_recover_from_yjs_encoder() {
677 let yrs_options = Options {
678 client_id: rand::random(),
679 guid: nanoid::nanoid!().into(),
680 ..Default::default()
681 };
682
683 loom_model!({
684 let binary = {
685 let doc = yrs::Doc::with_options(yrs_options.clone());
686 let text = doc.get_or_insert_text("greating");
687 let mut trx = doc.transact_mut();
688 text.insert(&mut trx, 0, "hello");
689 text.insert(&mut trx, 5, " world!");
690 text.remove_range(&mut trx, 11, 1);
691
692 trx.encode_update_v1()
693 };
694 #[allow(clippy::needless_borrow)]
696 let doc = Doc::try_from_binary_v1(&binary).unwrap();
697 let mut text = doc.get_or_create_text("greating").unwrap();
698
699 assert_eq!(text.to_string(), "hello world");
700
701 text.insert(6, "great ").unwrap();
702 text.insert(17, '!').unwrap();
703 assert_eq!(text.to_string(), "hello great world!");
704 });
705 }
706
707 #[test]
708 fn test_recover_from_octobase_encoder() {
709 loom_model!({
710 let binary = {
711 let doc = Doc::new();
712 let mut text = doc.get_or_create_text("greating").unwrap();
713 text.insert(0, "hello").unwrap();
714 text.insert(5, " world!").unwrap();
715 text.remove(11, 1).unwrap();
716
717 doc.encode_update_v1().unwrap()
718 };
719
720 let doc = Doc::try_from_binary_v1(binary).unwrap();
721 let mut text = doc.get_or_create_text("greating").unwrap();
722
723 assert_eq!(text.to_string(), "hello world");
724
725 text.insert(6, "great ").unwrap();
726 text.insert(17, '!').unwrap();
727 assert_eq!(text.to_string(), "hello great world!");
728 });
729 }
730
731 #[test]
732 fn test_text_delta_insert_format() {
733 loom_model!({
734 let doc = Doc::new();
735 let mut text = doc.get_or_create_text("text").unwrap();
736
737 let mut attrs = TextAttributes::new();
738 attrs.insert("bold".to_string(), Any::True);
739
740 text.apply_delta(&[TextDeltaOp::Insert {
741 insert: TextInsert::Text("abc".to_string()),
742 format: Some(attrs.clone()),
743 }])
744 .unwrap();
745
746 assert_eq!(text.to_string(), "abc");
747 assert_eq!(
748 text.to_delta(),
749 vec![TextDeltaOp::Insert {
750 insert: TextInsert::Text("abc".to_string()),
751 format: Some(attrs),
752 }]
753 );
754 });
755 }
756
757 #[test]
758 fn test_text_delta_retain_format() {
759 loom_model!({
760 let doc = Doc::new();
761 let mut text = doc.get_or_create_text("text").unwrap();
762
763 text.apply_delta(&[TextDeltaOp::Insert {
764 insert: TextInsert::Text("abc".to_string()),
765 format: None,
766 }])
767 .unwrap();
768
769 let mut attrs = TextAttributes::new();
770 attrs.insert("bold".to_string(), Any::True);
771
772 text.apply_delta(&[TextDeltaOp::Retain {
773 retain: 1,
774 format: Some(attrs.clone()),
775 }])
776 .unwrap();
777
778 assert_eq!(
779 text.to_delta(),
780 vec![
781 TextDeltaOp::Insert {
782 insert: TextInsert::Text("a".to_string()),
783 format: Some(attrs),
784 },
785 TextDeltaOp::Insert {
786 insert: TextInsert::Text("bc".to_string()),
787 format: None,
788 }
789 ]
790 );
791 });
792 }
793
794 #[test]
795 fn test_text_delta_utf16_retain() {
796 loom_model!({
797 let doc = Doc::new();
798 let mut text = doc.get_or_create_text("text").unwrap();
799
800 text.apply_delta(&[TextDeltaOp::Insert {
801 insert: TextInsert::Text("😀".to_string()),
802 format: None,
803 }])
804 .unwrap();
805
806 let mut attrs = TextAttributes::new();
807 attrs.insert("bold".to_string(), Any::True);
808
809 text.apply_delta(&[TextDeltaOp::Retain {
810 retain: 2,
811 format: Some(attrs.clone()),
812 }])
813 .unwrap();
814
815 assert_eq!(
816 text.to_delta(),
817 vec![TextDeltaOp::Insert {
818 insert: TextInsert::Text("😀".to_string()),
819 format: Some(attrs),
820 }]
821 );
822 });
823 }
824}