oficina / docs Public

Download this file

1	use crate::block::{EmbedPrelim, Item, ItemContent, ItemPosition, ItemPtr, Prelim, Unused};
2	use crate::transaction::TransactionMut;
3	use crate::types::{
4	AsPrelim, Attrs, Branch, BranchPtr, DefaultPrelim, Delta, Out, Path, RootRef, SharedRef,
5	TypePtr, TypeRef,
6	};
7	use crate::utils::OptionExt;
8	use crate::*;
9	use std::cell::UnsafeCell;
10	use std::collections::HashMap;
11	use std::convert::{TryFrom, TryInto};
12	use std::fmt::Formatter;
13	use std::ops::{Deref, DerefMut};
14
15	/// A shared data type used for collaborative text editing. It enables multiple users to add and
16	/// remove chunks of text in efficient manner. This type is internally represented as a mutable
17	/// double-linked list of text chunks - an optimization occurs during [Transaction::commit], which
18	/// allows to squash multiple consecutively inserted characters together as a single chunk of text
19	/// even between transaction boundaries in order to preserve more efficient memory model.
20	///
21	/// [TextRef] structure internally uses UTF-8 encoding and its length is described in a number of
22	/// bytes rather than individual characters (a single UTF-8 code point can consist of many bytes).
23	///
24	/// Like all Yrs shared data types, [TextRef] is resistant to the problem of interleaving (situation
25	/// when characters inserted one after another may interleave with other peers concurrent inserts
26	/// after merging all updates together). In case of Yrs conflict resolution is solved by using
27	/// unique document id to determine correct and consistent ordering.
28	///
29	/// [TextRef] offers a rich text editing capabilities (it's not limited to simple text operations).
30	/// Actions like embedding objects, binaries (eg. images) and formatting attributes are all possible
31	/// using [TextRef].
32	///
33	/// Keep in mind that [TextRef::get_string] method returns a raw string, stripped of formatting
34	/// attributes or embedded objects. If there's a need to include them, use [TextRef::diff] method
35	/// instead.
36	///
37	/// Another note worth reminding is that human-readable numeric indexes are not good for maintaining
38	/// cursor positions in rich text documents with real-time collaborative capabilities. In such cases
39	/// any concurrent update incoming and applied from the remote peer may change the order of elements
40	/// in current [TextRef], invalidating numeric index. For such cases you can take advantage of fact
41	/// that [TextRef] implements [IndexedSequence::sticky_index] method that returns a
42	/// [permanent index](StickyIndex) position that sticks to the same place even when concurrent
43	/// updates are being made.
44	///
45	/// # Example
46	///
47	/// ```rust
48	/// use yrs::{Any, Array, ArrayPrelim, Doc, GetString, Text, Transact};
49	/// use yrs::types::Attrs;
50	/// use yrs::types::text::{Diff, YChange};
51	///
52	/// let doc = Doc::new();
53	/// let text = doc.get_or_insert_text("article");
54	/// let mut txn = doc.transact_mut();
55	///
56	/// let bold = Attrs::from([("b".into(), true.into())]);
57	/// let italic = Attrs::from([("i".into(), true.into())]);
58	///
59	/// text.insert(&mut txn, 0, "hello ");
60	/// text.insert_with_attributes(&mut txn, 6, "world", italic.clone());
61	/// text.format(&mut txn, 0, 5, bold.clone());
62	///
63	/// let chunks = text.diff(&txn, YChange::identity);
64	/// assert_eq!(chunks, vec![
65	/// Diff::new("hello".into(), Some(Box::new(bold.clone()))),
66	/// Diff::new(" ".into(), None),
67	/// Diff::new("world".into(), Some(Box::new(italic))),
68	/// ]);
69	///
70	/// // remove formatting
71	/// let remove_italic = Attrs::from([("i".into(), Any::Null)]);
72	/// text.format(&mut txn, 6, 5, remove_italic);
73	///
74	/// let chunks = text.diff(&txn, YChange::identity);
75	/// assert_eq!(chunks, vec![
76	/// Diff::new("hello".into(), Some(Box::new(bold.clone()))),
77	/// Diff::new(" world".into(), None),
78	/// ]);
79	///
80	/// // insert binary payload eg. images
81	/// let image = b"deadbeaf".to_vec();
82	/// text.insert_embed(&mut txn, 1, image);
83	///
84	/// // insert nested shared type eg. table as ArrayRef of ArrayRefs
85	/// let table = text.insert_embed(&mut txn, 5, ArrayPrelim::default());
86	/// let header = table.insert(&mut txn, 0, ArrayPrelim::from(["Book title", "Author"]));
87	/// let row = table.insert(&mut txn, 1, ArrayPrelim::from(["\"Moby-Dick\"", "Herman Melville"]));
88	/// ```
89	#[repr(transparent)]
90	#[derive(Debug, Clone)]
91	pub struct TextRef(BranchPtr);
92
93	impl RootRef for TextRef {
94	fn type_ref() -> TypeRef {
95	TypeRef::Text
96	}
97	}
98	impl SharedRef for TextRef {}
99	impl Text for TextRef {}
100	impl IndexedSequence for TextRef {}
101	#[cfg(feature = "weak")]
102	impl crate::Quotable for TextRef {}
103
104	impl AsRef<XmlTextRef> for TextRef {
105	#[inline]
106	fn as_ref(&self) -> &XmlTextRef {
107	unsafe { std::mem::transmute(self) }
108	}
109	}
110
111	impl DeepObservable for TextRef {}
112	impl Observable for TextRef {
113	type Event = TextEvent;
114	}
115
116	impl GetString for TextRef {
117	/// Converts context of this text data structure into a single string value. This method doesn't
118	/// render formatting attributes or embedded content. In order to retrieve it, use
119	/// [TextRef::diff] method.
120	fn get_string<T: ReadTxn>(&self, _txn: &T) -> String {
121	let mut start = self.0.start;
122	let mut s = String::new();
123	while let Some(item) = start.as_deref() {
124	if !item.is_deleted() {
125	if let ItemContent::String(item_string) = &item.content {
126	s.push_str(item_string);
127	}
128	}
129	start = item.right.clone();
130	}
131	s
132	}
133	}
134
135	impl TryFrom<ItemPtr> for TextRef {
136	type Error = ItemPtr;
137
138	fn try_from(value: ItemPtr) -> Result<Self, Self::Error> {
139	if let Some(branch) = value.clone().as_branch() {
140	Ok(TextRef::from(branch))
141	} else {
142	Err(value)
143	}
144	}
145	}
146
147	impl TryFrom<Out> for TextRef {
148	type Error = Out;
149
150	fn try_from(value: Out) -> Result<Self, Self::Error> {
151	match value {
152	Out::YText(value) => Ok(value),
153	other => Err(other),
154	}
155	}
156	}
157
158	pub trait Text: AsRef<Branch> + Sized {
159	/// Returns a number of characters visible in a current text data structure.
160	fn len<T: ReadTxn>(&self, _txn: &T) -> u32 {
161	self.as_ref().content_len
162	}
163
164	/// Inserts a `chunk` of text at a given `index`.
165	/// If `index` is `0`, this `chunk` will be inserted at the beginning of a current text.
166	/// If `index` is equal to current data structure length, this `chunk` will be appended at
167	/// the end of it.
168	///
169	/// This method will panic if provided `index` is greater than the length of a current text.
170	///
171	/// # Examples
172	///
173	/// By default Document uses byte offset:
174	///
175	/// ```
176	/// use yrs::{Doc, Text, GetString, Transact};
177	///
178	/// let doc = Doc::new();
179	/// let ytext = doc.get_or_insert_text("text");
180	/// let txn = &mut doc.transact_mut();
181	/// ytext.push(txn, "Hi ★ to you");
182	///
183	/// // The same as `String::len()`
184	/// assert_eq!(ytext.len(txn), 13);
185	///
186	/// // To insert you have to count bytes and not chars.
187	/// ytext.insert(txn, 6, "!");
188	/// assert_eq!(ytext.get_string(txn), "Hi ★! to you");
189	/// ```
190	///
191	/// You can override how Yrs calculates the index with [OffsetKind]:
192	///
193	/// ```
194	/// use yrs::{Doc, Options, Text, GetString, Transact, OffsetKind};
195	///
196	/// let doc = Doc::with_options(Options {
197	/// offset_kind: OffsetKind::Utf16,
198	/// ..Default::default()
199	/// });
200	/// let ytext = doc.get_or_insert_text("text");
201	/// let txn = &mut doc.transact_mut();
202	/// ytext.push(txn, "Hi ★ to you");
203	///
204	/// // The same as `String::chars()::count()`
205	/// assert_eq!(ytext.len(txn), 11);
206	///
207	/// // To insert you have to count chars.
208	/// ytext.insert(txn, 4, "!");
209	/// assert_eq!(ytext.get_string(txn), "Hi ★! to you");
210	/// ```
211	///
212	fn insert(&self, txn: &mut TransactionMut, index: u32, chunk: &str) {
213	if chunk.is_empty() {
214	return;
215	}
216	let this = BranchPtr::from(self.as_ref());
217	if let Some(mut pos) = find_position(this, txn, index) {
218	let value = crate::block::PrelimString(chunk.into());
219	while let Some(right) = pos.right.as_ref() {
220	if right.is_deleted() {
221	// skip over deleted blocks, just like Yjs does
222	pos.forward();
223	} else {
224	break;
225	}
226	}
227	txn.create_item(&pos, value, None);
228	} else {
229	panic!("The type or the position doesn't exist!");
230	}
231	}
232
233	fn apply_delta<D, P>(&self, txn: &mut TransactionMut, delta: D)
234	where
235	D: IntoIterator<Item = Delta<P>>,
236	P: Prelim,
237	{
238	let branch = BranchPtr::from(self.as_ref());
239	let mut pos = ItemPosition {
240	parent: TypePtr::Branch(branch),
241	left: None,
242	right: branch.start,
243	index: 0,
244	current_attrs: Some(Box::new(Attrs::new())),
245	};
246	for delta in delta {
247	match delta {
248	Delta::Inserted(value, attrs) => {
249	let attrs: Attrs = match attrs {
250	None => Attrs::new(),
251	Some(attrs) => *attrs,
252	};
253	insert(branch, txn, &mut pos, DeltaChunk(value), attrs);
254	}
255	Delta::Deleted(len) => remove(txn, &mut pos, len),
256	Delta::Retain(len, attrs) => {
257	let attrs: Attrs = match attrs {
258	None => Attrs::new(),
259	Some(attrs) => *attrs,
260	};
261	insert_format(branch, txn, &mut pos, len, attrs);
262	}
263	}
264	}
265	}
266
267	/// Inserts a `chunk` of text at a given `index`.
268	/// If `index` is `0`, this `chunk` will be inserted at the beginning of a current text.
269	/// If `index` is equal to current data structure length, this `chunk` will be appended at
270	/// the end of it.
271	/// Collection of supplied `attributes` will be used to wrap provided text `chunk` range with a
272	/// formatting blocks.
273	///
274	/// This method will panic if provided `index` is greater than the length of a current text.
275	fn insert_with_attributes(
276	&self,
277	txn: &mut TransactionMut,
278	index: u32,
279	chunk: &str,
280	attributes: Attrs,
281	) {
282	if chunk.is_empty() {
283	return;
284	}
285	let this = BranchPtr::from(self.as_ref());
286	if let Some(mut pos) = find_position(this, txn, index) {
287	let value = block::PrelimString(chunk.into());
288	insert(this, txn, &mut pos, value, attributes);
289	} else {
290	panic!("The type or the position doesn't exist!");
291	}
292	}
293
294	/// Inserts an embed `content` at a given `index`.
295	///
296	/// If `index` is `0`, this `content` will be inserted at the beginning of a current text.
297	/// If `index` is equal to current data structure length, this `embed` will be appended at
298	/// the end of it.
299	///
300	/// This method will panic if provided `index` is greater than the length of a current text.
301	fn insert_embed<V>(&self, txn: &mut TransactionMut, index: u32, content: V) -> V::Return
302	where
303	V: Into<EmbedPrelim<V>> + Prelim,
304	{
305	let this = BranchPtr::from(self.as_ref());
306	if let Some(pos) = find_position(this, txn, index) {
307	let ptr = txn
308	.create_item(&pos, content.into(), None)
309	.expect("cannot insert empty value");
310	if let Ok(integrated) = ptr.try_into() {
311	integrated
312	} else {
313	panic!("Defect: embedded return type doesn't match.")
314	}
315	} else {
316	panic!("The type or the position doesn't exist!");
317	}
318	}
319
320	/// Inserts an embed `content` of text at a given `index`.
321	/// If `index` is `0`, this `content` will be inserted at the beginning of a current text.
322	/// If `index` is equal to current data structure length, this `chunk` will be appended at
323	/// the end of it.
324	/// Collection of supplied `attributes` will be used to wrap provided text `content` range with
325	/// a formatting blocks.
326	///
327	/// This method will panic if provided `index` is greater than the length of a current text.
328	fn insert_embed_with_attributes<V>(
329	&self,
330	txn: &mut TransactionMut,
331	index: u32,
332	embed: V,
333	attributes: Attrs,
334	) -> V::Return
335	where
336	V: Into<EmbedPrelim<V>> + Prelim,
337	{
338	let this = BranchPtr::from(self.as_ref());
339	if let Some(mut pos) = find_position(this, txn, index) {
340	let item = insert(this, txn, &mut pos, embed.into(), attributes)
341	.expect("cannot insert empty value");
342	if let Ok(integrated) = item.try_into() {
343	integrated
344	} else {
345	panic!("Defect: unexpected returned integrated type")
346	}
347	} else {
348	panic!("The type or the position doesn't exist!");
349	}
350	}
351
352	/// Appends a given `chunk` of text at the end of a current text structure.
353	fn push(&self, txn: &mut TransactionMut, chunk: &str) {
354	let idx = self.len(txn);
355	self.insert(txn, idx, chunk)
356	}
357
358	/// Removes up to a `len` characters from a current text structure, starting at given `index`.
359	/// This method panics in case when not all expected characters were removed (due to
360	/// insufficient number of characters to remove) or `index` is outside of the bounds of text.
361	fn remove_range(&self, txn: &mut TransactionMut, index: u32, len: u32) {
362	let this = BranchPtr::from(self.as_ref());
363	if let Some(mut pos) = find_position(this, txn, index) {
364	remove(txn, &mut pos, len)
365	} else {
366	panic!("The type or the position doesn't exist!");
367	}
368	}
369
370	/// Wraps an existing piece of text within a range described by `index`-`len` parameters with
371	/// formatting blocks containing provided `attributes` metadata.
372	fn format(&self, txn: &mut TransactionMut, index: u32, len: u32, attributes: Attrs) {
373	let this = BranchPtr::from(self.as_ref());
374	if let Some(mut pos) = find_position(this, txn, index) {
375	insert_format(this, txn, &mut pos, len, attributes)
376	} else {
377	panic!("Index {} is outside of the range.", index);
378	}
379	}
380
381	/// Returns an ordered sequence of formatted chunks, current [Text] corresponds of. These chunks
382	/// may contain inserted pieces of text or more complex elements like embedded binaries of
383	/// shared objects. Chunks are organized by type of inserted value and formatting attributes
384	/// wrapping it around. If formatting attributes are nested into each other, they will be split
385	/// into separate [Diff] chunks.
386	///
387	/// `compute_ychange` callback is used to attach custom data to produced chunks.
388	///
389	/// # Example
390	///
391	/// ```rust
392	/// use yrs::{Doc, Text, Transact};
393	/// use yrs::types::Attrs;
394	/// use yrs::types::text::{Diff, YChange};
395	///
396	/// let doc = Doc::new();
397	/// let text = doc.get_or_insert_text("article");
398	/// let mut txn = doc.transact_mut();
399	///
400	/// let bold = Attrs::from([("b".into(), true.into())]);
401	/// let italic = Attrs::from([("i".into(), true.into())]);
402	///
403	/// text.insert_with_attributes(&mut txn, 0, "hello world", italic.clone()); // "<i>hello world</i>"
404	/// text.format(&mut txn, 6, 5, bold.clone()); // "<i>hello <b>world</b></i>"
405	/// let image = vec![0, 0, 0, 0];
406	/// text.insert_embed(&mut txn, 5, image.clone()); // insert binary after "hello"
407	///
408	/// let italic_and_bold = Attrs::from([
409	/// ("b".into(), true.into()),
410	/// ("i".into(), true.into())
411	/// ]);
412	/// let chunks = text.diff(&txn, YChange::identity);
413	/// assert_eq!(chunks, vec![
414	/// Diff::new("hello".into(), Some(Box::new(italic.clone()))),
415	/// Diff::new(image.into(), Some(Box::new(italic.clone()))),
416	/// Diff::new(" ".into(), Some(Box::new(italic))),
417	/// Diff::new("world".into(), Some(Box::new(italic_and_bold))),
418	/// ]);
419	/// ```
420	fn diff<T, D, F>(&self, _txn: &T, compute_ychange: F) -> Vec<Diff<D>>
421	where
422	T: ReadTxn,
423	F: Fn(YChange) -> D,
424	{
425	let mut asm = DiffAssembler::new(compute_ychange);
426	asm.process(self.as_ref().start, None, None, None, None);
427	asm.finish()
428	}
429
430	/// Returns the Delta representation of this YText type.
431	fn diff_range<D, F>(
432	&self,
433	txn: &mut TransactionMut,
434	hi: Option<&Snapshot>,
435	lo: Option<&Snapshot>,
436	compute_ychange: F,
437	) -> Vec<Diff<D>>
438	where
439	F: Fn(YChange) -> D,
440	{
441	if let Some(snapshot) = hi {
442	txn.split_by_snapshot(snapshot);
443	}
444	if let Some(snapshot) = lo {
445	txn.split_by_snapshot(snapshot);
446	}
447
448	let mut asm = DiffAssembler::new(compute_ychange);
449	asm.process(self.as_ref().start, hi, lo, None, None);
450	asm.finish()
451	}
452	}
453
454	impl From<BranchPtr> for TextRef {
455	fn from(inner: BranchPtr) -> Self {
456	TextRef(inner)
457	}
458	}
459
460	impl AsRef<Branch> for TextRef {
461	fn as_ref(&self) -> &Branch {
462	self.0.deref()
463	}
464	}
465
466	impl AsPrelim for TextRef {
467	type Prelim = DeltaPrelim;
468
469	fn as_prelim<T: ReadTxn>(&self, txn: &T) -> Self::Prelim {
470	let delta: Vec<Delta<In>> = self
471	.diff(txn, YChange::identity)
472	.into_iter()
473	.map(|diff| Delta::Inserted(diff.insert.as_prelim(txn), diff.attributes))
474	.collect();
475	DeltaPrelim(delta)
476	}
477	}
478
479	impl DefaultPrelim for TextRef {
480	type Prelim = TextPrelim;
481
482	#[inline]
483	fn default_prelim() -> Self::Prelim {
484	TextPrelim::default()
485	}
486	}
487
488	impl Eq for TextRef {}
489	impl PartialEq for TextRef {
490	fn eq(&self, other: &Self) -> bool {
491	self.0.id() == other.0.id()
492	}
493	}
494
495	struct DeltaChunk<P>(P);
496
497	impl<P> Prelim for DeltaChunk<P>
498	where
499	P: Prelim,
500	{
501	type Return = Unused;
502
503	fn into_content(self, txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
504	let (content, rest) = self.0.into_content(txn);
505	match content {
506	ItemContent::Any(mut any) if any.len() == 1 => match any.pop().unwrap() {
507	Any::String(str) => (ItemContent::String(str.as_ref().into()), None),
508	other => (ItemContent::Embed(other), None),
509	},
510	other => (other, rest.map(DeltaChunk)),
511	}
512	}
513
514	fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
515	self.0.integrate(txn, inner_ref)
516	}
517	}
518
519	struct DiffAssembler<D, F>
520	where
521	F: Fn(YChange) -> D,
522	{
523	ops: Vec<Diff<D>>,
524	buf: String,
525	curr_attrs: Attrs,
526	curr_ychange: Option<YChange>,
527	compute_ychange: F,
528	}
529
530	impl<T, F> DiffAssembler<T, F>
531	where
532	F: Fn(YChange) -> T,
533	{
534	fn new(compute_ychange: F) -> Self {
535	DiffAssembler {
536	ops: Vec::new(),
537	buf: String::new(),
538	curr_attrs: HashMap::new(),
539	curr_ychange: None,
540	compute_ychange,
541	}
542	}
543	fn pack_str(&mut self) {
544	if !self.buf.is_empty() {
545	let attrs = self.attrs_boxed();
546	let mut buf = std::mem::replace(&mut self.buf, String::new());
547	buf.shrink_to_fit();
548	let change = if let Some(ychange) = self.curr_ychange.take() {
549	Some((self.compute_ychange)(ychange))
550	} else {
551	None
552	};
553	let op = Diff::with_change(Out::Any(buf.into()), attrs, change);
554	self.ops.push(op);
555	}
556	}
557
558	fn finish(self) -> Vec<Diff<T>> {
559	self.ops
560	}
561
562	fn attrs_boxed(&mut self) -> Option<Box<Attrs>> {
563	if self.curr_attrs.is_empty() {
564	None
565	} else {
566	Some(Box::new(self.curr_attrs.clone()))
567	}
568	}
569	fn process(
570	&mut self,
571	mut n: Option<ItemPtr>,
572	hi: Option<&Snapshot>,
573	lo: Option<&Snapshot>,
574	start: Option<&StickyIndex>,
575	end: Option<&StickyIndex>,
576	) {
577	fn seen(snapshot: Option<&Snapshot>, item: &Item) -> bool {
578	if let Some(s) = snapshot {
579	s.is_visible(&item.id)
580	} else {
581	!item.is_deleted()
582	}
583	}
584	let (start, start_assoc) = if let Some(index) = start {
585	(index.id(), index.assoc)
586	} else {
587	(None, Assoc::Before)
588	};
589	let (end, end_assoc) = if let Some(index) = end {
590	(index.id(), index.assoc)
591	} else {
592	(None, Assoc::After)
593	};
594
595	let mut start_offset: i32 = if start.is_none() { 0 } else { -1 };
596	'LOOP: while let Some(item) = n.as_deref() {
597	if let Some(start) = start {
598	if start_offset < 0 && item.contains(start) {
599	if start_assoc == Assoc::After {
600	if start.clock == item.id.clock + item.len() - 1 {
601	start_offset = 0;
602	n = item.right;
603	continue;
604	} else {
605	start_offset = start.clock as i32 - item.id.clock as i32 + 1;
606	}
607	} else {
608	start_offset = start.clock as i32 - item.id.clock as i32;
609	}
610	}
611	}
612	if let Some(end) = end {
613	if end_assoc == Assoc::Before && &item.id == end {
614	break;
615	}
616	}
617	if seen(hi, item) || (lo.is_some() && seen(lo, item)) {
618	match &item.content {
619	ItemContent::String(s) => {
620	if let Some(snapshot) = hi {
621	if !snapshot.is_visible(&item.id) {
622	self.pack_str();
623	self.curr_ychange =
624	Some(YChange::new(ChangeKind::Removed, item.id));
625	} else if let Some(snapshot) = lo {
626	if !snapshot.is_visible(&item.id) {
627	self.pack_str();
628	self.curr_ychange =
629	Some(YChange::new(ChangeKind::Added, item.id));
630	} else if self.curr_ychange.is_some() {
631	self.pack_str();
632	}
633	}
634	}
635	if start_offset > 0 {
636	let slice = &s.as_str()[start_offset as usize..];
637	self.buf.push_str(slice);
638	start_offset = 0;
639	} else {
640	match end {
641	Some(end) if item.contains(end) => {
642	// we reached the end or range
643	let mut end_offset =
644	(item.id.clock + item.len - end.clock - 1) as usize;
645	if end_assoc == Assoc::Before {
646	end_offset -= 1;
647	}
648	let s = s.as_str();
649	let slice = &s[..(s.len() + end_offset)];
650	self.buf.push_str(slice);
651	self.pack_str();
652	break 'LOOP;
653	}
654	_ => {
655	if start_offset == 0 {
656	self.buf.push_str(s.as_str());
657	}
658	}
659	}
660	}
661	}
662	ItemContent::Type(_) | ItemContent::Embed(_) => {
663	self.pack_str();
664	if let Some(value) = item.content.get_first() {
665	let attrs = self.attrs_boxed();
666	self.ops.push(Diff::new(value, attrs));
667	}
668	}
669	ItemContent::Format(key, value) => {
670	if seen(hi, item) {
671	self.pack_str();
672	update_current_attributes(&mut self.curr_attrs, key, value.as_ref());
673	}
674	}
675	_ => {}
676	}
677	} else if let Some(end) = end {
678	if item.contains(end) {
679	break;
680	}
681	}
682	n = item.right;
683	}
684
685	self.pack_str();
686	}
687	}
688
689	pub(crate) fn diff_between<D, F>(
690	ptr: Option<ItemPtr>,
691	start: Option<&StickyIndex>,
692	end: Option<&StickyIndex>,
693	compute_ychange: F,
694	) -> Vec<Diff<D>>
695	where
696	F: Fn(YChange) -> D,
697	{
698	let mut asm = DiffAssembler::new(compute_ychange);
699	asm.process(ptr, None, None, start, end);
700	asm.finish()
701	}
702
703	fn insert<P: Prelim>(
704	branch: BranchPtr,
705	txn: &mut TransactionMut,
706	pos: &mut ItemPosition,
707	value: P,
708	mut attributes: Attrs,
709	) -> Option<ItemPtr> {
710	pos.unset_missing(&mut attributes);
711	minimize_attr_changes(pos, &attributes);
712	let negated_attrs = insert_attributes(branch, txn, pos, attributes);
713
714	let item = if let Some(item) = txn.create_item(&pos, value, None) {
715	pos.right = Some(item);
716	pos.forward();
717	Some(item)
718	} else {
719	None
720	};
721
722	insert_negated_attributes(branch, txn, pos, negated_attrs);
723	item
724	}
725
726	pub(crate) fn update_current_attributes(attrs: &mut Attrs, key: &str, value: &Any) {
727	if let Any::Null = value {
728	attrs.remove(key);
729	} else {
730	attrs.insert(key.into(), value.clone());
731	}
732	}
733
734	fn find_position(this: BranchPtr, txn: &mut TransactionMut, index: u32) -> Option<ItemPosition> {
735	let mut pos = {
736	ItemPosition {
737	parent: this.into(),
738	left: None,
739	right: this.start,
740	index: 0,
741	current_attrs: None,
742	}
743	};
744
745	let mut format_ptrs = HashMap::new();
746	let store = txn.store_mut();
747	let encoding = store.offset_kind;
748	let mut remaining = index;
749	while let Some(right) = pos.right {
750	if remaining == 0 {
751	break;
752	}
753
754	if !right.is_deleted() {
755	match &right.content {
756	ItemContent::Format(key, value) => {
757	if let Any::Null = value.as_ref() {
758	format_ptrs.remove(key);
759	} else {
760	format_ptrs.insert(key.clone(), pos.right.clone());
761	}
762	}
763	_ => {
764	let mut block_len = right.len();
765	let content_len = right.content_len(encoding);
766	if remaining < content_len {
767	// split right item
768	let offset = if let ItemContent::String(str) = &right.content {
769	str.block_offset(remaining, encoding)
770	} else {
771	remaining
772	};
773	store
774	.blocks
775	.split_block(right, offset, OffsetKind::Utf16)
776	.unwrap();
777	block_len -= offset;
778	remaining = 0;
779	} else {
780	remaining -= content_len;
781	}
782	pos.index += block_len;
783	}
784	}
785	}
786	pos.left = pos.right.take();
787	pos.right = if let Some(item) = pos.left.as_deref() {
788	item.right
789	} else {
790	None
791	};
792	}
793
794	for (_, block_ptr) in format_ptrs {
795	if let Some(item) = block_ptr {
796	if let ItemContent::Format(key, value) = &item.content {
797	let attrs = pos.current_attrs.get_or_init();
798	update_current_attributes(attrs, key, value.as_ref());
799	}
800	}
801	}
802
803	Some(pos)
804	}
805
806	fn remove(txn: &mut TransactionMut, pos: &mut ItemPosition, len: u32) {
807	let encoding = txn.store().offset_kind;
808	let mut remaining = len;
809	let start = pos.right.clone();
810	let start_attrs = pos.current_attrs.clone();
811	while let Some(item) = pos.right.as_deref() {
812	if remaining == 0 {
813	break;
814	}
815
816	if !item.is_deleted() {
817	match &item.content {
818	ItemContent::Embed(_) | ItemContent::String(_) | ItemContent::Type(_) => {
819	let content_len = item.content_len(encoding);
820	let ptr = pos.right.unwrap();
821	if remaining < content_len {
822	// split block
823	let offset = if let ItemContent::String(s) = &item.content {
824	s.block_offset(remaining, encoding)
825	} else {
826	len
827	};
828	remaining = 0;
829	txn.store_mut()
830	.blocks
831	.split_block(ptr, offset, OffsetKind::Utf16);
832	} else {
833	remaining -= content_len;
834	};
835	txn.delete(ptr);
836	}
837	_ => {}
838	}
839	}
840
841	pos.forward();
842	}
843
844	if remaining > 0 {
845	panic!(
846	"Couldn't remove {} elements from an array. Only {} of them were successfully removed.",
847	len,
848	len - remaining
849	);
850	}
851
852	if let (Some(start), Some(start_attrs), Some(end_attrs)) =
853	(start, start_attrs, pos.current_attrs.as_mut())
854	{
855	clean_format_gap(
856	txn,
857	Some(start),
858	pos.right,
859	start_attrs.as_ref(),
860	end_attrs.as_mut(),
861	);
862	}
863	}
864
865	fn is_valid_target(item: ItemPtr) -> bool {
866	if item.is_deleted() {
867	true
868	} else if let ItemContent::Format(_, _) = &item.content {
869	true
870	} else {
871	false
872	}
873	}
874
875	fn insert_format(
876	this: BranchPtr,
877	txn: &mut TransactionMut,
878	pos: &mut ItemPosition,
879	mut len: u32,
880	attrs: Attrs,
881	) {
882	minimize_attr_changes(pos, &attrs);
883	let mut negated_attrs = insert_attributes(this, txn, pos, attrs.clone()); //TODO: remove `attrs.clone()`
884	let encoding = txn.store().offset_kind;
885	// iterate until first non-format or null is found
886	// delete all formats with attributes[format.key] != null
887	// also check the attributes after the first non-format as we do not want to insert redundant
888	// negated attributes there
889	while let Some(right) = pos.right {
890	if !(len > 0 || (!negated_attrs.is_empty() && is_valid_target(right))) {
891	break;
892	}
893
894	if !right.is_deleted() {
895	match &right.content {
896	ItemContent::Format(key, value) => {
897	if let Some(v) = attrs.get(key) {
898	if v == value.as_ref() {
899	negated_attrs.remove(key);
900	} else {
901	negated_attrs.insert(key.clone(), *value.clone());
902	}
903	txn.delete(right);
904	}
905	}
906	ItemContent::String(s) => {
907	let content_len = right.content_len(encoding);
908	if len < content_len {
909	// split block
910	let offset = s.block_offset(len, encoding);
911	let new_right =
912	txn.store_mut()
913	.blocks
914	.split_block(right, offset, OffsetKind::Utf16);
915	pos.left = Some(right);
916	pos.right = new_right;
917	break;
918	}
919	len -= content_len;
920	}
921	_ => {
922	let content_len = right.len();
923	if len < content_len {
924	let new_right =
925	txn.store_mut()
926	.blocks
927	.split_block(right, len, OffsetKind::Utf16);
928	pos.left = Some(right);
929	pos.right = new_right;
930	break;
931	}
932	len -= content_len;
933	}
934	}
935	}
936
937	if !pos.forward() {
938	break;
939	}
940	}
941
942	insert_negated_attributes(this, txn, pos, negated_attrs);
943	}
944
945	fn minimize_attr_changes(pos: &mut ItemPosition, attrs: &Attrs) {
946	// go right while attrs[right.key] === right.value (or right is deleted)
947	while let Some(i) = pos.right.as_deref() {
948	if !i.is_deleted() {
949	if let ItemContent::Format(k, v) = &i.content {
950	if let Some(v2) = attrs.get(k) {
951	if (v.as_ref()).eq(v2) {
952	pos.forward();
953	continue;
954	}
955	}
956	}
957
958	break;
959	} else {
960	pos.forward();
961	}
962	}
963	}
964
965	fn insert_attributes(
966	this: BranchPtr,
967	txn: &mut TransactionMut,
968	pos: &mut ItemPosition,
969	attrs: Attrs,
970	) -> Attrs {
971	let mut negated_attrs = HashMap::with_capacity(attrs.len());
972	let mut store = txn.store_mut();
973	for (k, v) in attrs {
974	let current_value = pos
975	.current_attrs
976	.as_ref()
977	.and_then(|a| a.get(&k))
978	.unwrap_or(&Any::Null);
979	if &v != current_value {
980	// save negated attribute (set null if currentVal undefined)
981	negated_attrs.insert(k.clone(), current_value.clone());
982
983	let client_id = store.client_id;
984	let parent = this.into();
985	let mut item = Item::new(
986	ID::new(client_id, store.blocks.get_clock(&client_id)),
987	pos.left.clone(),
988	pos.left.map(|ptr| ptr.last_id()),
989	pos.right.clone(),
990	pos.right.map(|ptr| ptr.id().clone()),
991	parent,
992	None,
993	ItemContent::Format(k, v.into()),
994	)
995	.unwrap();
996	let mut item_ptr = ItemPtr::from(&mut item);
997	pos.right = Some(item_ptr);
998	item_ptr.integrate(txn, 0);
999	txn.store_mut().blocks.push_block(item);
1000
1001	pos.forward();
1002	store = txn.store_mut();
1003	}
1004	}
1005	negated_attrs
1006	}
1007
1008	fn insert_negated_attributes(
1009	this: BranchPtr,
1010	txn: &mut TransactionMut,
1011	pos: &mut ItemPosition,
1012	mut attrs: Attrs,
1013	) {
1014	while let Some(item) = pos.right.as_deref() {
1015	if !item.is_deleted() {
1016	if let ItemContent::Format(key, value) = &item.content {
1017	if let Some(curr_val) = attrs.get(key) {
1018	if curr_val == value.as_ref() {
1019	attrs.remove(key);
1020	pos.forward();
1021	continue;
1022	}
1023	}
1024	}
1025
1026	break;
1027	} else {
1028	pos.forward();
1029	}
1030	}
1031
1032	let mut store = txn.store_mut();
1033	for (k, v) in attrs {
1034	let client_id = store.client_id;
1035	let parent = this.into();
1036	let mut item = Item::new(
1037	ID::new(client_id, store.blocks.get_clock(&client_id)),
1038	pos.left.clone(),
1039	pos.left.map(|ptr| ptr.last_id()),
1040	pos.right.clone(),
1041	pos.right.map(|ptr| ptr.id().clone()),
1042	parent,
1043	None,
1044	ItemContent::Format(k, v.into()),
1045	)
1046	.unwrap();
1047	let mut item_ptr = ItemPtr::from(&mut item);
1048	pos.right = Some(item_ptr);
1049	item_ptr.integrate(txn, 0);
1050
1051	txn.store_mut().blocks.push_block(item);
1052
1053	pos.forward();
1054	store = txn.store_mut();
1055	}
1056	}
1057
1058	fn clean_format_gap(
1059	txn: &mut TransactionMut,
1060	mut start: Option<ItemPtr>,
1061	mut end: Option<ItemPtr>,
1062	start_attrs: &Attrs,
1063	end_attrs: &mut Attrs,
1064	) -> u32 {
1065	while let Some(item) = end.as_deref() {
1066	match &item.content {
1067	ItemContent::String(_) | ItemContent::Embed(_) => break,
1068	ItemContent::Format(key, value) if !item.is_deleted() => {
1069	update_current_attributes(end_attrs, key.as_ref(), value);
1070	}
1071	_ => {}
1072	}
1073	end = item.right.clone();
1074	}
1075
1076	let mut cleanups = 0;
1077	while start != end {
1078	if let Some(item) = start.as_deref() {
1079	let right = item.right.clone();
1080	if !item.is_deleted() {
1081	if let ItemContent::Format(key, value) = &item.content {
1082	let e = end_attrs.get(key).unwrap_or(&Any::Null);
1083	let s = start_attrs.get(key).unwrap_or(&Any::Null);
1084	if e != value.as_ref() || s == value.as_ref() {
1085	txn.delete(start.unwrap());
1086	cleanups += 1;
1087	}
1088	}
1089	}
1090	start = right;
1091	} else {
1092	break;
1093	}
1094	}
1095	cleanups
1096	}
1097
1098	/// A representation of an uniformly-formatted chunk of rich context stored by [TextRef] or
1099	/// [XmlTextRef]. It contains a value (which could be a string, embedded object or another shared
1100	/// type) with optional formatting attributes wrapping around this chunk. It can also contain some
1101	/// custom data generated by caller as part of [TextRef::diff] callback.
1102	#[derive(Debug, PartialEq)]
1103	pub struct Diff<T> {
1104	/// Inserted chunk of data. It can be (usually) piece of text, but possibly also embedded value
1105	/// or another shared type.
1106	pub insert: Out,
1107
1108	/// Optional formatting attributes wrapping inserted chunk of data.
1109	pub attributes: Option<Box<Attrs>>,
1110
1111	/// Custom user data attached to this chunk of data.
1112	pub ychange: Option<T>,
1113	}
1114
1115	impl<T> Diff<T> {
1116	pub fn new(insert: Out, attributes: Option<Box<Attrs>>) -> Self {
1117	Self::with_change(insert, attributes, None)
1118	}
1119
1120	pub fn with_change(insert: Out, attributes: Option<Box<Attrs>>, ychange: Option<T>) -> Self {
1121	Diff {
1122	insert,
1123	attributes,
1124	ychange,
1125	}
1126	}
1127	}
1128
1129	impl<T> From<Diff<T>> for Delta {
1130	#[inline]
1131	fn from(value: Diff<T>) -> Self {
1132	Delta::Inserted(value.insert, value.attributes)
1133	}
1134	}
1135
1136	#[repr(transparent)]
1137	#[derive(Debug, Clone, PartialEq, Default)]
1138	pub struct DeltaPrelim(Vec<Delta<In>>);
1139
1140	impl Deref for DeltaPrelim {
1141	type Target = [Delta<In>];
1142
1143	#[inline]
1144	fn deref(&self) -> &Self::Target {
1145	&self.0
1146	}
1147	}
1148
1149	impl Prelim for DeltaPrelim {
1150	type Return = TextRef;
1151
1152	fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
1153	(ItemContent::Type(Branch::new(TypeRef::Text)), Some(self))
1154	}
1155
1156	fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
1157	let text_ref = TextRef::from(inner_ref);
1158	text_ref.apply_delta(txn, self.0);
1159	}
1160	}
1161
1162	impl From<TextPrelim> for DeltaPrelim {
1163	fn from(value: TextPrelim) -> Self {
1164	DeltaPrelim(vec![Delta::Inserted(
1165	In::Any(Any::String(value.0.into())),
1166	None,
1167	)])
1168	}
1169	}
1170
1171	impl<T> std::fmt::Display for Diff<T> {
1172	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
1173	write!(f, "{{ insert: '{}'", self.insert)?;
1174	if let Some(attrs) = self.attributes.as_ref() {
1175	write!(f, ", attributes: {{")?;
1176	let mut i = attrs.iter();
1177	if let Some((k, v)) = i.next() {
1178	write!(f, " {}={}", k, v)?;
1179	}
1180	for (k, v) in i {
1181	write!(f, ", {}={}", k, v)?;
1182	}
1183	write!(f, " }}")?;
1184	}
1185	write!(f, " }}")
1186	}
1187	}
1188
1189	#[derive(Debug, Clone, PartialEq)]
1190	pub struct YChange {
1191	pub kind: ChangeKind,
1192	pub id: ID,
1193	}
1194
1195	impl YChange {
1196	pub fn new(kind: ChangeKind, id: ID) -> Self {
1197	YChange { kind, id }
1198	}
1199
1200	#[inline]
1201	pub fn identity(change: YChange) -> YChange {
1202	change
1203	}
1204	}
1205
1206	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1207	pub enum ChangeKind {
1208	Added,
1209	Removed,
1210	}
1211
1212	/// Event generated by [Text::observe] method. Emitted during transaction commit phase.
1213	pub struct TextEvent {
1214	pub(crate) current_target: BranchPtr,
1215	target: TextRef,
1216	delta: UnsafeCell<Option<Vec<Delta>>>,
1217	}
1218
1219	impl TextEvent {
1220	pub(crate) fn new(branch_ref: BranchPtr) -> Self {
1221	let current_target = branch_ref.clone();
1222	let target = TextRef::from(branch_ref);
1223	TextEvent {
1224	target,
1225	current_target,
1226	delta: UnsafeCell::new(None),
1227	}
1228	}
1229
1230	/// Returns a [Text] instance which emitted this event.
1231	pub fn target(&self) -> &TextRef {
1232	&self.target
1233	}
1234
1235	/// Returns a path from root type down to [Text] instance which emitted this event.
1236	pub fn path(&self) -> Path {
1237	Branch::path(self.current_target, self.target.0)
1238	}
1239
1240	/// Returns a summary of text changes made over corresponding [Text] collection within
1241	/// bounds of current transaction.
1242	pub fn delta(&self, txn: &TransactionMut) -> &[Delta] {
1243	let delta = unsafe { self.delta.get().as_mut().unwrap() };
1244	delta
1245	.get_or_insert_with(|| Self::get_delta(self.target.0, txn))
1246	.as_slice()
1247	}
1248
1249	pub(crate) fn get_delta(target: BranchPtr, txn: &TransactionMut) -> Vec<Delta> {
1250	#[derive(Debug, Clone, Copy, Eq, PartialEq)]
1251	enum Action {
1252	Insert,
1253	Retain,
1254	Delete,
1255	}
1256
1257	#[derive(Debug, Default)]
1258	struct DeltaAssembler {
1259	action: Option<Action>,
1260	insert: Option<Out>,
1261	insert_string: Option<String>,
1262	retain: u32,
1263	delete: u32,
1264	attrs: Attrs,
1265	current_attrs: Attrs,
1266	delta: Vec<Delta>,
1267	}
1268
1269	impl DeltaAssembler {
1270	fn add_op(&mut self) {
1271	match self.action.take() {
1272	None => {}
1273	Some(Action::Delete) => {
1274	let len = self.delete;
1275	self.delete = 0;
1276	self.delta.push(Delta::Deleted(len))
1277	}
1278	Some(Action::Insert) => {
1279	let value = if let Some(str) = self.insert.take() {
1280	str
1281	} else {
1282	let value = self.insert_string.take().unwrap();
1283	Any::from(value).into()
1284	};
1285	let attrs = if self.current_attrs.is_empty() {
1286	None
1287	} else {
1288	Some(Box::new(self.current_attrs.clone()))
1289	};
1290	self.delta.push(Delta::Inserted(value, attrs))
1291	}
1292	Some(Action::Retain) => {
1293	let len = self.retain;
1294	self.retain = 0;
1295	let attrs = if self.attrs.is_empty() {
1296	None
1297	} else {
1298	Some(Box::new(self.attrs.clone()))
1299	};
1300	self.delta.push(Delta::Retain(len, attrs));
1301	}
1302	}
1303	}
1304
1305	fn finish(mut self) -> Vec<Delta> {
1306	while let Some(last) = self.delta.pop() {
1307	match last {
1308	Delta::Retain(_, None) => {
1309	// retain delta's if they don't assign attributes
1310	}
1311	other => {
1312	self.delta.push(other);
1313	return self.delta;
1314	}
1315	}
1316	}
1317	self.delta
1318	}
1319	}
1320
1321	let encoding = txn.store().offset_kind;
1322	let mut old_attrs = HashMap::new();
1323	let mut asm = DeltaAssembler::default();
1324	let mut current = target.start;
1325
1326	while let Some(item) = current.as_deref() {
1327	match &item.content {
1328	ItemContent::Type(_) | ItemContent::Embed(_) => {
1329	if txn.has_added(&item.id) {
1330	if !txn.has_deleted(&item.id) {
1331	asm.add_op();
1332	asm.action = Some(Action::Insert);
1333	asm.insert = item.content.get_last();
1334	asm.add_op();
1335	}
1336	} else if txn.has_deleted(&item.id) {
1337	if asm.action != Some(Action::Delete) {
1338	asm.add_op();
1339	asm.action = Some(Action::Delete);
1340	}
1341	asm.delete += 1;
1342	} else if !item.is_deleted() {
1343	if asm.action != Some(Action::Retain) {
1344	asm.add_op();
1345	asm.action = Some(Action::Retain);
1346	}
1347	asm.retain += 1;
1348	}
1349	}
1350	ItemContent::String(s) => {
1351	if txn.has_added(&item.id) {
1352	if !txn.has_deleted(&item.id) {
1353	if asm.action != Some(Action::Insert) {
1354	asm.add_op();
1355	asm.action = Some(Action::Insert);
1356	}
1357	let buf = asm.insert_string.get_or_insert_with(String::default);
1358	buf.push_str(s.as_str());
1359	}
1360	} else if txn.has_deleted(&item.id) {
1361	if asm.action != Some(Action::Delete) {
1362	asm.add_op();
1363	asm.action = Some(Action::Delete);
1364	}
1365	let content_len = item.content_len(encoding);
1366	asm.delete += content_len;
1367	} else if !item.is_deleted() {
1368	if asm.action != Some(Action::Retain) {
1369	asm.add_op();
1370	asm.action = Some(Action::Retain);
1371	}
1372	asm.retain += item.content_len(encoding);
1373	}
1374	}
1375	ItemContent::Format(key, value) => {
1376	if txn.has_added(&item.id) {
1377	if !txn.has_deleted(&item.id) {
1378	let current_val = asm.current_attrs.get(key);
1379	if current_val != Some(value) {
1380	if asm.action == Some(Action::Retain) {
1381	asm.add_op();
1382	}
1383	match old_attrs.get(key) {
1384	None if value.as_ref() == &Any::Null => {
1385	asm.attrs.remove(key);
1386	}
1387	Some(v) if v == value => {
1388	asm.attrs.remove(key);
1389	}
1390	_ => {
1391	asm.attrs.insert(key.clone(), *value.clone());
1392	}
1393	}
1394	} else {
1395	// item.delete(transaction)
1396	}
1397	}
1398	} else if txn.has_deleted(&item.id) {
1399	old_attrs.insert(key.clone(), value.clone());
1400	let current_val = asm.current_attrs.get(key).unwrap_or(&Any::Null);
1401	if current_val != value.as_ref() {
1402	let curr_val_clone = current_val.clone();
1403	if asm.action == Some(Action::Retain) {
1404	asm.add_op();
1405	}
1406	asm.attrs.insert(key.clone(), curr_val_clone);
1407	}
1408	} else if !item.is_deleted() {
1409	old_attrs.insert(key.clone(), value.clone());
1410	let attr = asm.attrs.get(key);
1411	if let Some(attr) = attr {
1412	if attr != value.as_ref() {
1413	if asm.action == Some(Action::Retain) {
1414	asm.add_op();
1415	}
1416	if value.as_ref() == &Any::Null {
1417	asm.attrs.remove(key);
1418	} else {
1419	asm.attrs.insert(key.clone(), *value.clone());
1420	}
1421	} else {
1422	// item.delete(transaction)
1423	}
1424	}
1425	}
1426
1427	if !item.is_deleted() {
1428	if asm.action == Some(Action::Insert) {
1429	asm.add_op();
1430	}
1431	update_current_attributes(&mut asm.current_attrs, key, value.as_ref());
1432	}
1433	}
1434	_ => {}
1435	}
1436
1437	current = item.right;
1438	}
1439
1440	asm.add_op();
1441	asm.finish()
1442	}
1443	}
1444
1445	/// A preliminary text. It's can be used to initialize a [TextRef], when it's about to be nested
1446	/// into another Yrs data collection, such as [Map] or [Array].
1447	#[repr(transparent)]
1448	#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
1449	pub struct TextPrelim(String);
1450
1451	impl TextPrelim {
1452	#[inline]
1453	pub fn new<S: Into<String>>(value: S) -> Self {
1454	TextPrelim(value.into())
1455	}
1456	}
1457
1458	impl Deref for TextPrelim {
1459	type Target = String;
1460
1461	#[inline]
1462	fn deref(&self) -> &Self::Target {
1463	&self.0
1464	}
1465	}
1466
1467	impl DerefMut for TextPrelim {
1468	#[inline]
1469	fn deref_mut(&mut self) -> &mut Self::Target {
1470	&mut self.0
1471	}
1472	}
1473
1474	impl From<TextPrelim> for In {
1475	#[inline]
1476	fn from(value: TextPrelim) -> Self {
1477	In::Text(DeltaPrelim::from(value))
1478	}
1479	}
1480
1481	impl Prelim for TextPrelim {
1482	type Return = TextRef;
1483
1484	fn into_content(self, _txn: &mut TransactionMut) -> (ItemContent, Option<Self>) {
1485	let inner = Branch::new(TypeRef::Text);
1486	(ItemContent::Type(inner), Some(self))
1487	}
1488
1489	fn integrate(self, txn: &mut TransactionMut, inner_ref: BranchPtr) {
1490	if !self.0.is_empty() {
1491	let text = TextRef::from(inner_ref);
1492	text.push(txn, &self.0);
1493	}
1494	}
1495	}
1496
1497	impl Into<EmbedPrelim<TextPrelim>> for TextPrelim {
1498	#[inline]
1499	fn into(self) -> EmbedPrelim<TextPrelim> {
1500	EmbedPrelim::Shared(self)
1501	}
1502	}
1503
1504	#[cfg(test)]
1505	mod test {
1506	use crate::doc::{OffsetKind, Options};
1507	use crate::test_utils::{exchange_updates, run_scenario, RngExt};
1508	use crate::transaction::ReadTxn;
1509	use crate::types::text::{Attrs, ChangeKind, Delta, Diff, YChange};
1510	use crate::types::Out;
1511	use crate::updates::decoder::Decode;
1512	use crate::updates::encoder::{Encode, Encoder, EncoderV1};
1513	use crate::{
1514	any, Any, ArrayPrelim, Doc, GetString, Map, MapPrelim, MapRef, Observable, StateVector,
1515	Text, Transact, Update, WriteTxn, ID,
1516	};
1517	use arc_swap::ArcSwapOption;
1518	use fastrand::Rng;
1519	use std::collections::HashMap;
1520	use std::sync::atomic::{AtomicBool, Ordering};
1521	use std::sync::Arc;
1522	use std::time::Duration;
1523
1524	#[test]
1525	fn insert_empty_string() {
1526	let doc = Doc::new();
1527	let txt = doc.get_or_insert_text("test");
1528	let mut txn = doc.transact_mut();
1529
1530	assert_eq!(txt.get_string(&txn).as_str(), "");
1531
1532	txt.push(&mut txn, "");
1533	assert_eq!(txt.get_string(&txn).as_str(), "");
1534
1535	txt.push(&mut txn, "abc");
1536	txt.push(&mut txn, "");
1537	assert_eq!(txt.get_string(&txn).as_str(), "abc");
1538	}
1539
1540	#[test]
1541	fn append_single_character_blocks() {
1542	let doc = Doc::new();
1543	let txt = doc.get_or_insert_text("test");
1544	let mut txn = doc.transact_mut();
1545
1546	txt.insert(&mut txn, 0, "a");
1547	txt.insert(&mut txn, 1, "b");
1548	txt.insert(&mut txn, 2, "c");
1549
1550	assert_eq!(txt.get_string(&txn).as_str(), "abc");
1551	}
1552
1553	#[test]
1554	fn append_mutli_character_blocks() {
1555	let doc = Doc::new();
1556	let txt = doc.get_or_insert_text("test");
1557	let mut txn = doc.transact_mut();
1558
1559	txt.insert(&mut txn, 0, "hello");
1560	txt.insert(&mut txn, 5, " ");
1561	txt.insert(&mut txn, 6, "world");
1562
1563	assert_eq!(txt.get_string(&txn).as_str(), "hello world");
1564	}
1565
1566	#[test]
1567	fn prepend_single_character_blocks() {
1568	let doc = Doc::new();
1569	let txt = doc.get_or_insert_text("test");
1570	let mut txn = doc.transact_mut();
1571
1572	txt.insert(&mut txn, 0, "a");
1573	txt.insert(&mut txn, 0, "b");
1574	txt.insert(&mut txn, 0, "c");
1575
1576	assert_eq!(txt.get_string(&txn).as_str(), "cba");
1577	}
1578
1579	#[test]
1580	fn prepend_mutli_character_blocks() {
1581	let doc = Doc::new();
1582	let txt = doc.get_or_insert_text("test");
1583	let mut txn = doc.transact_mut();
1584
1585	txt.insert(&mut txn, 0, "hello");
1586	txt.insert(&mut txn, 0, " ");
1587	txt.insert(&mut txn, 0, "world");
1588
1589	assert_eq!(txt.get_string(&txn).as_str(), "world hello");
1590	}
1591
1592	#[test]
1593	fn insert_after_block() {
1594	let doc = Doc::new();
1595	let txt = doc.get_or_insert_text("test");
1596	let mut txn = doc.transact_mut();
1597
1598	txt.insert(&mut txn, 0, "hello");
1599	txt.insert(&mut txn, 5, " ");
1600	txt.insert(&mut txn, 6, "world");
1601	txt.insert(&mut txn, 6, "beautiful ");
1602
1603	assert_eq!(txt.get_string(&txn).as_str(), "hello beautiful world");
1604	}
1605
1606	#[test]
1607	fn insert_inside_of_block() {
1608	let doc = Doc::new();
1609	let txt = doc.get_or_insert_text("test");
1610	let mut txn = doc.transact_mut();
1611
1612	txt.insert(&mut txn, 0, "it was expected");
1613	txt.insert(&mut txn, 6, " not");
1614
1615	assert_eq!(txt.get_string(&txn).as_str(), "it was not expected");
1616	}
1617
1618	#[test]
1619	fn insert_concurrent_root() {
1620	let d1 = Doc::with_client_id(1);
1621	let txt1 = d1.get_or_insert_text("test");
1622	let mut t1 = d1.transact_mut();
1623
1624	txt1.insert(&mut t1, 0, "hello ");
1625
1626	let d2 = Doc::with_client_id(2);
1627	let txt2 = d2.get_or_insert_text("test");
1628	let mut t2 = d2.transact_mut();
1629
1630	txt2.insert(&mut t2, 0, "world");
1631
1632	let d1_sv = t1.state_vector().encode_v1();
1633	let d2_sv = t2.state_vector().encode_v1();
1634
1635	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&d2_sv).unwrap());
1636	let u2 = t2.encode_diff_v1(&StateVector::decode_v1(&d1_sv).unwrap());
1637
1638	t1.apply_update(Update::decode_v1(u2.as_slice()).unwrap())
1639	.unwrap();
1640	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1641	.unwrap();
1642
1643	let a = txt1.get_string(&t1);
1644	let b = txt2.get_string(&t2);
1645
1646	assert_eq!(a, b);
1647	assert_eq!(a.as_str(), "hello world");
1648	}
1649
1650	#[test]
1651	fn insert_concurrent_in_the_middle() {
1652	let d1 = Doc::with_client_id(1);
1653	let txt1 = d1.get_or_insert_text("test");
1654	let mut t1 = d1.transact_mut();
1655
1656	txt1.insert(&mut t1, 0, "I expect that");
1657	assert_eq!(txt1.get_string(&t1).as_str(), "I expect that");
1658
1659	let d2 = Doc::with_client_id(2);
1660	let txt2 = d2.get_or_insert_text("test");
1661	let mut t2 = d2.transact_mut();
1662
1663	let d2_sv = t2.state_vector().encode_v1();
1664	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&d2_sv).unwrap());
1665	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1666	.unwrap();
1667
1668	assert_eq!(txt2.get_string(&t2).as_str(), "I expect that");
1669
1670	txt2.insert(&mut t2, 1, " have");
1671	txt2.insert(&mut t2, 13, "ed");
1672	assert_eq!(txt2.get_string(&t2).as_str(), "I have expected that");
1673
1674	txt1.insert(&mut t1, 1, " didn't");
1675	assert_eq!(txt1.get_string(&t1).as_str(), "I didn't expect that");
1676
1677	let d2_sv = t2.state_vector().encode_v1();
1678	let d1_sv = t1.state_vector().encode_v1();
1679	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&d2_sv.as_slice()).unwrap());
1680	let u2 = t2.encode_diff_v1(&StateVector::decode_v1(&d1_sv.as_slice()).unwrap());
1681	t1.apply_update(Update::decode_v1(u2.as_slice()).unwrap())
1682	.unwrap();
1683	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1684	.unwrap();
1685
1686	let a = txt1.get_string(&t1);
1687	let b = txt2.get_string(&t2);
1688
1689	assert_eq!(a, b);
1690	assert_eq!(a.as_str(), "I didn't have expected that");
1691	}
1692
1693	#[test]
1694	fn append_concurrent() {
1695	let d1 = Doc::with_client_id(1);
1696	let txt1 = d1.get_or_insert_text("test");
1697	let mut t1 = d1.transact_mut();
1698
1699	txt1.insert(&mut t1, 0, "aaa");
1700	assert_eq!(txt1.get_string(&t1).as_str(), "aaa");
1701
1702	let d2 = Doc::with_client_id(2);
1703	let txt2 = d2.get_or_insert_text("test");
1704	let mut t2 = d2.transact_mut();
1705
1706	let d2_sv = t2.state_vector().encode_v1();
1707	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&d2_sv.as_slice()).unwrap());
1708	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1709	.unwrap();
1710
1711	assert_eq!(txt2.get_string(&t2).as_str(), "aaa");
1712
1713	txt2.insert(&mut t2, 3, "bbb");
1714	txt2.insert(&mut t2, 6, "bbb");
1715	assert_eq!(txt2.get_string(&t2).as_str(), "aaabbbbbb");
1716
1717	txt1.insert(&mut t1, 3, "aaa");
1718	assert_eq!(txt1.get_string(&t1).as_str(), "aaaaaa");
1719
1720	let d2_sv = t2.state_vector().encode_v1();
1721	let d1_sv = t1.state_vector().encode_v1();
1722	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&d2_sv.as_slice()).unwrap());
1723	let u2 = t2.encode_diff_v1(&StateVector::decode_v1(&d1_sv.as_slice()).unwrap());
1724
1725	t1.apply_update(Update::decode_v1(u2.as_slice()).unwrap())
1726	.unwrap();
1727	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1728	.unwrap();
1729
1730	let a = txt1.get_string(&t1);
1731	let b = txt2.get_string(&t2);
1732
1733	assert_eq!(a.as_str(), "aaaaaabbbbbb");
1734	assert_eq!(a, b);
1735	}
1736
1737	#[test]
1738	fn delete_single_block_start() {
1739	let doc = Doc::new();
1740	let txt = doc.get_or_insert_text("test");
1741	let mut txn = doc.transact_mut();
1742
1743	txt.insert(&mut txn, 0, "bbb");
1744	txt.insert(&mut txn, 0, "aaa");
1745	txt.remove_range(&mut txn, 0, 3);
1746
1747	assert_eq!(txt.len(&txn), 3);
1748	assert_eq!(txt.get_string(&txn).as_str(), "bbb");
1749	}
1750
1751	#[test]
1752	fn delete_single_block_end() {
1753	let doc = Doc::new();
1754	let txt = doc.get_or_insert_text("test");
1755	let mut txn = doc.transact_mut();
1756
1757	txt.insert(&mut txn, 0, "bbb");
1758	txt.insert(&mut txn, 0, "aaa");
1759	txt.remove_range(&mut txn, 3, 3);
1760
1761	assert_eq!(txt.get_string(&txn).as_str(), "aaa");
1762	}
1763
1764	#[test]
1765	fn delete_multiple_whole_blocks() {
1766	let doc = Doc::new();
1767	let txt = doc.get_or_insert_text("test");
1768	let mut txn = doc.transact_mut();
1769
1770	txt.insert(&mut txn, 0, "a");
1771	txt.insert(&mut txn, 1, "b");
1772	txt.insert(&mut txn, 2, "c");
1773
1774	txt.remove_range(&mut txn, 1, 1);
1775	assert_eq!(txt.get_string(&txn).as_str(), "ac");
1776
1777	txt.remove_range(&mut txn, 1, 1);
1778	assert_eq!(txt.get_string(&txn).as_str(), "a");
1779
1780	txt.remove_range(&mut txn, 0, 1);
1781	assert_eq!(txt.get_string(&txn).as_str(), "");
1782	}
1783
1784	#[test]
1785	fn delete_slice_of_block() {
1786	let doc = Doc::new();
1787	let txt = doc.get_or_insert_text("test");
1788	let mut txn = doc.transact_mut();
1789
1790	txt.insert(&mut txn, 0, "abc");
1791	txt.remove_range(&mut txn, 1, 1);
1792
1793	assert_eq!(txt.get_string(&txn).as_str(), "ac");
1794	}
1795
1796	#[test]
1797	fn delete_multiple_blocks_with_slicing() {
1798	let doc = Doc::new();
1799	let txt = doc.get_or_insert_text("test");
1800	let mut txn = doc.transact_mut();
1801
1802	txt.insert(&mut txn, 0, "hello ");
1803	txt.insert(&mut txn, 6, "beautiful");
1804	txt.insert(&mut txn, 15, " world");
1805
1806	txt.remove_range(&mut txn, 5, 11);
1807	assert_eq!(txt.get_string(&txn).as_str(), "helloworld");
1808	}
1809
1810	#[test]
1811	fn insert_after_delete() {
1812	let doc = Doc::new();
1813	let txt = doc.get_or_insert_text("test");
1814	let mut txn = doc.transact_mut();
1815
1816	txt.insert(&mut txn, 0, "hello ");
1817	txt.remove_range(&mut txn, 0, 5);
1818	txt.insert(&mut txn, 1, "world");
1819
1820	assert_eq!(txt.get_string(&txn).as_str(), " world");
1821	}
1822
1823	#[test]
1824	fn concurrent_insert_delete() {
1825	let d1 = Doc::with_client_id(1);
1826	let txt1 = d1.get_or_insert_text("test");
1827	let mut t1 = d1.transact_mut();
1828
1829	txt1.insert(&mut t1, 0, "hello world");
1830	assert_eq!(txt1.get_string(&t1).as_str(), "hello world");
1831
1832	let u1 = t1.encode_state_as_update_v1(&StateVector::default());
1833
1834	let d2 = Doc::with_client_id(2);
1835	let txt2 = d2.get_or_insert_text("test");
1836	let mut t2 = d2.transact_mut();
1837	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1838	.unwrap();
1839	assert_eq!(txt2.get_string(&t2).as_str(), "hello world");
1840
1841	txt1.insert(&mut t1, 5, " beautiful");
1842	txt1.insert(&mut t1, 21, "!");
1843	txt1.remove_range(&mut t1, 0, 5);
1844	assert_eq!(txt1.get_string(&t1).as_str(), " beautiful world!");
1845
1846	txt2.remove_range(&mut t2, 5, 5);
1847	txt2.remove_range(&mut t2, 0, 1);
1848	txt2.insert(&mut t2, 0, "H");
1849	assert_eq!(txt2.get_string(&t2).as_str(), "Hellod");
1850
1851	let sv1 = t1.state_vector().encode_v1();
1852	let sv2 = t2.state_vector().encode_v1();
1853	let u1 = t1.encode_diff_v1(&StateVector::decode_v1(&sv2.as_slice()).unwrap());
1854	let u2 = t2.encode_diff_v1(&StateVector::decode_v1(&sv1.as_slice()).unwrap());
1855
1856	t1.apply_update(Update::decode_v1(u2.as_slice()).unwrap())
1857	.unwrap();
1858	t2.apply_update(Update::decode_v1(u1.as_slice()).unwrap())
1859	.unwrap();
1860
1861	let a = txt1.get_string(&t1);
1862	let b = txt2.get_string(&t2);
1863
1864	assert_eq!(a, b);
1865	assert_eq!(a, "H beautifuld!".to_owned());
1866	}
1867
1868	#[test]
1869	fn observer() {
1870	let doc = Doc::with_client_id(1);
1871	let txt = doc.get_or_insert_text("text");
1872	let delta = Arc::new(ArcSwapOption::default());
1873	let delta_c = delta.clone();
1874	let sub = txt.observe(move |txn, e| {
1875	delta_c.store(Some(Arc::new(e.delta(txn).to_vec())));
1876	});
1877
1878	// insert initial data to an empty YText
1879	txt.insert(&mut doc.transact_mut(), 0, "abcd"); // => 'abcd'
1880	assert_eq!(
1881	delta.load_full(),
1882	Some(Arc::new(vec![Delta::Inserted("abcd".into(), None)]))
1883	);
1884
1885	// remove 2 chars from the middle
1886	txt.remove_range(&mut doc.transact_mut(), 1, 2); // => 'ad'
1887	assert_eq!(
1888	delta.load_full(),
1889	Some(Arc::new(vec![Delta::Retain(1, None), Delta::Deleted(2)]))
1890	);
1891
1892	// insert new item in the middle
1893	let attrs = Attrs::from([("bold".into(), true.into())]);
1894	txt.insert_with_attributes(&mut doc.transact_mut(), 1, "e", attrs.clone()); // => 'a<bold>e</bold>d'
1895	assert_eq!(
1896	delta.load_full(),
1897	Some(Arc::new(vec![
1898	Delta::Retain(1, None),
1899	Delta::Inserted("e".into(), Some(Box::new(attrs)))
1900	]))
1901	);
1902
1903	// remove formatting
1904	let attrs = Attrs::from([("bold".into(), Any::Null)]);
1905	txt.format(&mut doc.transact_mut(), 1, 1, attrs.clone()); // => 'aed'
1906	assert_eq!(
1907	delta.swap(None),
1908	Some(Arc::new(vec![
1909	Delta::Retain(1, None),
1910	Delta::Retain(2, Some(Box::new(attrs)))
1911	]))
1912	);
1913
1914	// free the observer and make sure that callback is no longer called
1915	drop(sub);
1916	txt.insert(&mut doc.transact_mut(), 1, "fgh"); // => 'afghed'
1917	assert_eq!(delta.swap(None), None);
1918	}
1919
1920	#[test]
1921	fn insert_and_remove_event_changes() {
1922	let d1 = Doc::with_client_id(1);
1923	let txt = d1.get_or_insert_text("text");
1924	let delta = Arc::new(ArcSwapOption::default());
1925	let delta_c = delta.clone();
1926	let _sub = txt.observe(move |txn, e| delta_c.store(Some(Arc::new(e.delta(txn).to_vec()))));
1927
1928	// insert initial string
1929	{
1930	let mut txn = d1.transact_mut();
1931	txt.insert(&mut txn, 0, "abcd");
1932	}
1933	assert_eq!(
1934	delta.swap(None),
1935	Some(Arc::new(vec![Delta::Inserted("abcd".into(), None)]))
1936	);
1937
1938	// remove middle
1939	{
1940	let mut txn = d1.transact_mut();
1941	txt.remove_range(&mut txn, 1, 2);
1942	}
1943	assert_eq!(
1944	delta.swap(None),
1945	Some(Arc::new(vec![Delta::Retain(1, None), Delta::Deleted(2)]))
1946	);
1947
1948	// insert again
1949	{
1950	let mut txn = d1.transact_mut();
1951	txt.insert(&mut txn, 1, "ef");
1952	}
1953	assert_eq!(
1954	delta.swap(None),
1955	Some(Arc::new(vec![
1956	Delta::Retain(1, None),
1957	Delta::Inserted("ef".into(), None)
1958	]))
1959	);
1960
1961	// replicate data to another peer
1962	let d2 = Doc::with_client_id(2);
1963	let txt = d2.get_or_insert_text("text");
1964	let delta_c = delta.clone();
1965	let _sub = txt.observe(move |txn, e| delta_c.store(Some(Arc::new(e.delta(txn).to_vec()))));
1966
1967	{
1968	let t1 = d1.transact_mut();
1969	let mut t2 = d2.transact_mut();
1970
1971	let sv = t2.state_vector();
1972	let mut encoder = EncoderV1::new();
1973	t1.encode_diff(&sv, &mut encoder);
1974	t2.apply_update(Update::decode_v1(encoder.to_vec().as_slice()).unwrap())
1975	.unwrap();
1976	}
1977
1978	assert_eq!(
1979	delta.swap(None),
1980	Some(Arc::new(vec![Delta::Inserted("aefd".into(), None)]))
1981	);
1982	}
1983
1984	fn text_transactions() -> [Box<dyn Fn(&mut Doc, &mut Rng)>; 2] {
1985	fn insert_text(doc: &mut Doc, rng: &mut Rng) {
1986	let ytext = doc.get_or_insert_text("text");
1987	let mut txn = doc.transact_mut();
1988	let pos = rng.between(0, ytext.len(&txn));
1989	let word = rng.random_string();
1990	ytext.insert(&mut txn, pos, word.as_str());
1991	}
1992
1993	fn delete_text(doc: &mut Doc, rng: &mut Rng) {
1994	let ytext = doc.get_or_insert_text("text");
1995	let mut txn = doc.transact_mut();
1996	let len = ytext.len(&txn);
1997	if len > 0 {
1998	let pos = rng.between(0, len - 1);
1999	let to_delete = rng.between(2, len - pos);
2000	ytext.remove_range(&mut txn, pos, to_delete);
2001	}
2002	}
2003
2004	[Box::new(insert_text), Box::new(delete_text)]
2005	}
2006
2007	fn fuzzy(iterations: usize) {
2008	run_scenario(0, &text_transactions(), 5, iterations)
2009	}
2010
2011	#[test]
2012	fn fuzzy_test_3() {
2013	fuzzy(3)
2014	}
2015
2016	#[test]
2017	fn basic_format() {
2018	let d1 = Doc::with_client_id(1);
2019	let txt1 = d1.get_or_insert_text("text");
2020
2021	let delta1 = Arc::new(ArcSwapOption::default());
2022	let delta_clone = delta1.clone();
2023	let _sub1 =
2024	txt1.observe(move |txn, e| delta_clone.store(Some(Arc::new(e.delta(txn).to_vec()))));
2025
2026	let d2 = Doc::with_client_id(2);
2027	let txt2 = d2.get_or_insert_text("text");
2028
2029	let delta2 = Arc::new(ArcSwapOption::default());
2030	let delta_clone = delta2.clone();
2031	let _sub2 =
2032	txt2.observe(move |txn, e| delta_clone.store(Some(Arc::new(e.delta(txn).to_vec()))));
2033
2034	let a: Attrs = HashMap::from([("bold".into(), Any::Bool(true))]);
2035
2036	// step 1
2037	{
2038	let mut txn = d1.transact_mut();
2039	txt1.insert_with_attributes(&mut txn, 0, "abc", a.clone());
2040	let update = txn.encode_update_v1();
2041	drop(txn);
2042
2043	let expected = Some(Arc::new(vec![Delta::Inserted(
2044	"abc".into(),
2045	Some(Box::new(a.clone())),
2046	)]));
2047
2048	assert_eq!(txt1.get_string(&d1.transact()), "abc".to_string());
2049	assert_eq!(
2050	txt1.diff(&d1.transact(), YChange::identity),
2051	vec![Diff::new("abc".into(), Some(Box::new(a.clone())))]
2052	);
2053	assert_eq!(delta1.swap(None), expected);
2054
2055	let mut txn = d2.transact_mut();
2056	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2057	.unwrap();
2058	drop(txn);
2059
2060	assert_eq!(txt2.get_string(&d2.transact()), "abc".to_string());
2061	assert_eq!(delta2.swap(None), expected);
2062	}
2063
2064	// step 2
2065	{
2066	let mut txn = d1.transact_mut();
2067	txt1.remove_range(&mut txn, 0, 1);
2068	let update = txn.encode_update_v1();
2069	drop(txn);
2070
2071	let expected = Some(Arc::new(vec![Delta::Deleted(1)]));
2072
2073	assert_eq!(txt1.get_string(&d1.transact()), "bc".to_string());
2074	assert_eq!(
2075	txt1.diff(&d1.transact(), YChange::identity),
2076	vec![Diff::new("bc".into(), Some(Box::new(a.clone())))]
2077	);
2078	assert_eq!(delta1.swap(None), expected);
2079
2080	let mut txn = d2.transact_mut();
2081	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2082	.unwrap();
2083	drop(txn);
2084
2085	assert_eq!(txt2.get_string(&d2.transact()), "bc".to_string());
2086	assert_eq!(delta2.swap(None), expected);
2087	}
2088
2089	// step 3
2090	{
2091	let mut txn = d1.transact_mut();
2092	txt1.remove_range(&mut txn, 1, 1);
2093	let update = txn.encode_update_v1();
2094	drop(txn);
2095
2096	let expected = Some(Arc::new(vec![Delta::Retain(1, None), Delta::Deleted(1)]));
2097
2098	assert_eq!(txt1.get_string(&d1.transact()), "b".to_string());
2099	assert_eq!(
2100	txt1.diff(&d1.transact(), YChange::identity),
2101	vec![Diff::new("b".into(), Some(Box::new(a.clone())))]
2102	);
2103	assert_eq!(delta1.swap(None), expected);
2104
2105	let mut txn = d2.transact_mut();
2106	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2107	.unwrap();
2108	drop(txn);
2109
2110	assert_eq!(txt2.get_string(&d2.transact()), "b".to_string());
2111	assert_eq!(delta2.swap(None), expected);
2112	}
2113
2114	// step 4
2115	{
2116	let mut txn = d1.transact_mut();
2117	txt1.insert_with_attributes(&mut txn, 0, "z", a.clone());
2118	let update = txn.encode_update_v1();
2119	drop(txn);
2120
2121	let expected = Some(Arc::new(vec![Delta::Inserted(
2122	"z".into(),
2123	Some(Box::new(a.clone())),
2124	)]));
2125
2126	assert_eq!(txt1.get_string(&d1.transact()), "zb".to_string());
2127	assert_eq!(
2128	txt1.diff(&mut d1.transact_mut(), YChange::identity),
2129	vec![Diff::new("zb".into(), Some(Box::new(a.clone())))]
2130	);
2131	assert_eq!(delta1.swap(None), expected);
2132
2133	let mut txn = d2.transact_mut();
2134	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2135	.unwrap();
2136	drop(txn);
2137
2138	assert_eq!(txt2.get_string(&d2.transact()), "zb".to_string());
2139	assert_eq!(delta2.swap(None), expected);
2140	}
2141
2142	// step 5
2143	{
2144	let mut txn = d1.transact_mut();
2145	txt1.insert(&mut txn, 0, "y");
2146	let update = txn.encode_update_v1();
2147	drop(txn);
2148
2149	let expected = Some(Arc::new(vec![Delta::Inserted("y".into(), None)]));
2150
2151	assert_eq!(txt1.get_string(&d1.transact()), "yzb".to_string());
2152	assert_eq!(
2153	txt1.diff(&mut d1.transact_mut(), YChange::identity),
2154	vec![
2155	Diff::new("y".into(), None),
2156	Diff::new("zb".into(), Some(Box::new(a.clone())))
2157	]
2158	);
2159	assert_eq!(delta1.swap(None), expected);
2160
2161	let mut txn = d2.transact_mut();
2162	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2163	.unwrap();
2164	drop(txn);
2165
2166	assert_eq!(txt2.get_string(&d2.transact()), "yzb".to_string());
2167	assert_eq!(delta2.swap(None), expected);
2168	}
2169
2170	// step 6
2171	{
2172	let mut txn = d1.transact_mut();
2173	let b: Attrs = HashMap::from([("bold".into(), Any::Null)]);
2174	txt1.format(&mut txn, 0, 2, b.clone());
2175	let update = txn.encode_update_v1();
2176	drop(txn);
2177
2178	let expected = Some(Arc::new(vec![
2179	Delta::Retain(1, None),
2180	Delta::Retain(1, Some(Box::new(b))),
2181	]));
2182
2183	assert_eq!(txt1.get_string(&d1.transact()), "yzb".to_string());
2184	assert_eq!(
2185	txt1.diff(&mut d1.transact_mut(), YChange::identity),
2186	vec![
2187	Diff::new("yz".into(), None),
2188	Diff::new("b".into(), Some(Box::new(a.clone())))
2189	]
2190	);
2191	assert_eq!(delta1.swap(None), expected);
2192
2193	let mut txn = d2.transact_mut();
2194	txn.apply_update(Update::decode_v1(update.as_slice()).unwrap())
2195	.unwrap();
2196	drop(txn);
2197
2198	assert_eq!(txt2.get_string(&d2.transact()), "yzb".to_string());
2199	assert_eq!(delta2.swap(None), expected);
2200	}
2201	}
2202
2203	#[test]
2204	fn embed_with_attributes() {
2205	let d1 = Doc::with_client_id(1);
2206	let txt1 = d1.get_or_insert_text("text");
2207
2208	let delta1 = Arc::new(ArcSwapOption::default());
2209	let delta_clone = delta1.clone();
2210	let _sub1 = txt1.observe(move |txn, e| {
2211	let delta = e.delta(txn).to_vec();
2212	delta_clone.store(Some(Arc::new(delta)));
2213	});
2214
2215	let a1: Attrs = HashMap::from([("bold".into(), true.into())]);
2216	let embed = any!({
2217	"image": "imageSrc.png"
2218	});
2219
2220	let (update_v1, update_v2) = {
2221	let mut txn = d1.transact_mut();
2222	txt1.insert_with_attributes(&mut txn, 0, "ab", a1.clone());
2223
2224	let a2: Attrs = HashMap::from([("width".into(), Any::Number(100.0))]);
2225
2226	txt1.insert_embed_with_attributes(&mut txn, 1, embed.clone(), a2.clone());
2227	drop(txn);
2228
2229	let a1 = Some(Box::new(a1.clone()));
2230	let a2 = Some(Box::new(a2.clone()));
2231
2232	let expected = Some(Arc::new(vec![
2233	Delta::Inserted("a".into(), a1.clone()),
2234	Delta::Inserted(embed.clone().into(), a2.clone()),
2235	Delta::Inserted("b".into(), a1.clone()),
2236	]));
2237	assert_eq!(delta1.swap(None), expected);
2238
2239	let expected = vec![
2240	Diff::new("a".into(), a1.clone()),
2241	Diff::new(embed.clone().into(), a2),
2242	Diff::new("b".into(), a1.clone()),
2243	];
2244	let mut txn = d1.transact_mut();
2245	assert_eq!(txt1.diff(&mut txn, YChange::identity), expected);
2246
2247	let update_v1 = txn.encode_state_as_update_v1(&StateVector::default());
2248	let update_v2 = txn.encode_state_as_update_v2(&StateVector::default());
2249	(update_v1, update_v2)
2250	};
2251
2252	let a1 = Some(Box::new(a1));
2253	let a2 = Some(Box::new(HashMap::from([(
2254	"width".into(),
2255	Any::Number(100.0),
2256	)])));
2257
2258	let expected = vec![
2259	Diff::new("a".into(), a1.clone()),
2260	Diff::new(embed.into(), a2),
2261	Diff::new("b".into(), a1.clone()),
2262	];
2263
2264	let d2 = Doc::new();
2265	let txt2 = d2.get_or_insert_text("text");
2266	{
2267	let txn = &mut d2.transact_mut();
2268	let update = Update::decode_v1(&update_v1).unwrap();
2269	txn.apply_update(update).unwrap();
2270	assert_eq!(txt2.diff(txn, YChange::identity), expected);
2271	}
2272
2273	let d3 = Doc::new();
2274	let txt3 = d3.get_or_insert_text("text");
2275	{
2276	let txn = &mut d3.transact_mut();
2277	let update = Update::decode_v2(&update_v2).unwrap();
2278	txn.apply_update(update).unwrap();
2279	let actual = txt3.diff(txn, YChange::identity);
2280	assert_eq!(actual, expected);
2281	}
2282	}
2283
2284	#[test]
2285	fn issue_101() {
2286	let d1 = Doc::with_client_id(1);
2287	let txt1 = d1.get_or_insert_text("text");
2288	let delta = Arc::new(ArcSwapOption::default());
2289	let delta_copy = delta.clone();
2290
2291	let attrs: Attrs = HashMap::from([("bold".into(), true.into())]);
2292
2293	txt1.insert(&mut d1.transact_mut(), 0, "abcd");
2294
2295	let _sub = txt1.observe(move |txn, e| {
2296	delta_copy.store(Some(e.delta(txn).to_vec().into()));
2297	});
2298	txt1.format(&mut d1.transact_mut(), 1, 2, attrs.clone());
2299
2300	let expected = Arc::new(vec![
2301	Delta::Retain(1, None),
2302	Delta::Retain(2, Some(Box::new(attrs))),
2303	]);
2304	let actual = delta.load_full();
2305	assert_eq!(actual, Some(expected));
2306	}
2307
2308	#[test]
2309	fn yrs_delete() {
2310	let doc = Doc::with_options(Options {
2311	offset_kind: OffsetKind::Utf16,
2312	..Default::default()
2313	});
2314
2315	let text1 = r#"
2316	Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Eleifend mi in nulla posuere sollicitudin. Lorem mollis aliquam ut porttitor. Enim ut sem viverra aliquet eget sit amet. Sed turpis tincidunt id aliquet risus feugiat in ante metus. Accumsan lacus vel facilisis volutpat. Non consectetur a erat nam at lectus urna. Enim diam vulputate ut pharetra sit amet. In dictum non consectetur a erat. Bibendum at varius vel pharetra vel turpis nunc eget lorem. Blandit cursus risus at ultrices. Sed lectus vestibulum mattis ullamcorper velit sed ullamcorper. Sagittis nisl rhoncus mattis rhoncus.
2317
2318	Sed vulputate odio ut enim. Erat pellentesque adipiscing commodo elit at imperdiet dui. Ultricies tristique nulla aliquet enim tortor at auctor urna nunc. Tincidunt eget nullam non nisi est sit amet. Sed adipiscing diam donec adipiscing tristique risus nec. Risus commodo viverra maecenas accumsan lacus vel facilisis volutpat est. Donec enim diam vulputate ut pharetra sit amet aliquam id. Netus et malesuada fames ac turpis egestas sed tempus urna. Augue mauris augue neque gravida. Tellus orci ac auctor augue mauris augue. Ante metus dictum at tempor. Feugiat in ante metus dictum at. Vitae elementum curabitur vitae nunc sed velit dignissim. Non arcu risus quis varius quam quisque id diam vel. Fermentum leo vel orci porta non. Donec adipiscing tristique risus nec feugiat in fermentum posuere. Duis convallis convallis tellus id interdum velit laoreet id. Vel eros donec ac odio tempor orci dapibus ultrices in. At varius vel pharetra vel turpis nunc eget lorem. Blandit aliquam etiam erat velit scelerisque in.
2319	"#;
2320
2321	let text2 = r#"test"#;
2322
2323	{
2324	let text = doc.get_or_insert_text("content");
2325	let mut txn = doc.transact_mut();
2326	text.insert(&mut txn, 0, text1);
2327	txn.commit();
2328	}
2329
2330	{
2331	let text = doc.get_or_insert_text("content");
2332	let mut txn = doc.transact_mut();
2333	text.insert(&mut txn, 100, text2);
2334	txn.commit();
2335	}
2336
2337	{
2338	let text = doc.get_or_insert_text("content");
2339	let mut txn = doc.transact_mut();
2340
2341	let c1 = text1.chars().count();
2342	let c2 = text2.chars().count();
2343	let count = c1 as u32 + c2 as u32;
2344
2345	let _observer = text
2346	.observe(move |txn, edit| assert_eq!(edit.delta(txn)[0], Delta::Deleted(count)));
2347
2348	text.remove_range(&mut txn, 0, count);
2349	txn.commit();
2350	}
2351
2352	{
2353	let text = doc.get_or_insert_text("content");
2354	assert_eq!(text.get_string(&doc.transact()), "");
2355	}
2356	}
2357
2358	#[test]
2359	fn text_diff_adjacent() {
2360	let doc = Doc::with_client_id(1);
2361	let txt = doc.get_or_insert_text("text");
2362	let mut txn = doc.transact_mut();
2363	let attrs1 = Attrs::from([("a".into(), "a".into())]);
2364	txt.insert_with_attributes(&mut txn, 0, "abc", attrs1.clone());
2365	let attrs2 = Attrs::from([("a".into(), "a".into()), ("b".into(), "b".into())]);
2366	txt.insert_with_attributes(&mut txn, 3, "def", attrs2.clone());
2367
2368	let diff = txt.diff(&mut txn, YChange::identity);
2369	let expected = vec![
2370	Diff::new("abc".into(), Some(Box::new(attrs1))),
2371	Diff::new("def".into(), Some(Box::new(attrs2))),
2372	];
2373	assert_eq!(diff, expected);
2374	}
2375
2376	#[test]
2377	fn text_remove_4_byte_range() {
2378	let d1 = Doc::new();
2379	let txt = d1.get_or_insert_text("test");
2380
2381	txt.insert(&mut d1.transact_mut(), 0, "😭😊");
2382
2383	let d2 = Doc::new();
2384	exchange_updates(&[&d1, &d2]);
2385
2386	txt.remove_range(&mut d1.transact_mut(), 0, "😭".len() as u32);
2387	assert_eq!(txt.get_string(&d1.transact()).as_str(), "😊");
2388
2389	exchange_updates(&[&d1, &d2]);
2390	let txt = d2.get_or_insert_text("test");
2391	assert_eq!(txt.get_string(&d2.transact()).as_str(), "😊");
2392	}
2393
2394	#[test]
2395	fn text_remove_3_byte_range() {
2396	let d1 = Doc::new();
2397	let txt = d1.get_or_insert_text("test");
2398
2399	txt.insert(&mut d1.transact_mut(), 0, "⏰⏳");
2400
2401	let d2 = Doc::new();
2402	exchange_updates(&[&d1, &d2]);
2403
2404	txt.remove_range(&mut d1.transact_mut(), 0, "⏰".len() as u32);
2405	assert_eq!(txt.get_string(&d1.transact()).as_str(), "⏳");
2406
2407	exchange_updates(&[&d1, &d2]);
2408	let txt = d2.get_or_insert_text("test");
2409	assert_eq!(txt.get_string(&d2.transact()).as_str(), "⏳");
2410	}
2411	#[test]
2412	fn delete_4_byte_character_from_middle() {
2413	let doc = Doc::new();
2414	let txt = doc.get_or_insert_text("test");
2415	let mut txn = doc.transact_mut();
2416
2417	txt.insert(&mut txn, 0, "😊😭");
2418	// uncomment the following line will pass the test
2419	// txt.format(&mut txn, 0, "😊".len() as u32, HashMap::new());
2420	txt.remove_range(&mut txn, "😊".len() as u32, "😭".len() as u32);
2421
2422	assert_eq!(txt.get_string(&txn).as_str(), "😊");
2423	}
2424
2425	#[test]
2426	fn delete_3_byte_character_from_middle_1() {
2427	let doc = Doc::new();
2428	let txt = doc.get_or_insert_text("test");
2429	let mut txn = doc.transact_mut();
2430
2431	txt.insert(&mut txn, 0, "⏰⏳");
2432	// uncomment the following line will pass the test
2433	// txt.format(&mut txn, 0, "⏰".len() as u32, HashMap::new());
2434	txt.remove_range(&mut txn, "⏰".len() as u32, "⏳".len() as u32);
2435
2436	assert_eq!(txt.get_string(&txn).as_str(), "⏰");
2437	}
2438
2439	#[test]
2440	fn delete_3_byte_character_from_middle_2() {
2441	let doc = Doc::new();
2442	let txt = doc.get_or_insert_text("test");
2443	let mut txn = doc.transact_mut();
2444
2445	txt.insert(&mut txn, 0, "👯🙇‍♀️🙇‍♀️⏰👩‍❤️‍💋‍👨");
2446
2447	txt.format(
2448	&mut txn,
2449	"👯".len() as u32,
2450	"🙇‍♀️🙇‍♀️".len() as u32,
2451	HashMap::new(),
2452	);
2453	txt.remove_range(&mut txn, "👯🙇‍♀️🙇‍♀️".len() as u32, "⏰".len() as u32); // will delete ⏰ and 👩‍❤️‍💋‍👨
2454
2455	assert_eq!(txt.get_string(&txn).as_str(), "👯🙇‍♀️🙇‍♀️👩‍❤️‍💋‍👨");
2456	}
2457
2458	#[test]
2459	fn delete_3_byte_character_from_middle_after_insert_and_format() {
2460	let doc = Doc::new();
2461	let txt = doc.get_or_insert_text("test");
2462	let mut txn = doc.transact_mut();
2463
2464	txt.insert(&mut txn, 0, "🙇‍♀️🙇‍♀️⏰👩‍❤️‍💋‍👨");
2465	txt.insert(&mut txn, 0, "👯");
2466	txt.format(
2467	&mut txn,
2468	"👯".len() as u32,
2469	"🙇‍♀️🙇‍♀️".len() as u32,
2470	HashMap::new(),
2471	);
2472
2473	// will delete ⏰ and 👩‍❤️‍💋‍👨
2474	txt.remove_range(&mut txn, "👯🙇‍♀️🙇‍♀️".len() as u32, "⏰".len() as u32); // will delete ⏰ and 👩‍❤️‍💋‍👨
2475
2476	assert_eq!(&txt.get_string(&txn), "👯🙇‍♀️🙇‍♀️👩‍❤️‍💋‍👨");
2477	}
2478
2479	#[test]
2480	fn delete_multi_byte_character_from_middle_after_insert_and_format() {
2481	let doc = Doc::with_client_id(1);
2482	let txt = doc.get_or_insert_text("test");
2483	let mut txn = doc.transact_mut();
2484
2485	txt.insert(&mut txn, 0, "❤️❤️🙇‍♀️🙇‍♀️⏰👩‍❤️‍💋‍👨👩‍❤️‍💋‍👨");
2486	txt.insert(&mut txn, 0, "👯");
2487	txt.format(
2488	&mut txn,
2489	"👯".len() as u32,
2490	"❤️❤️🙇‍♀️🙇‍♀️⏰".len() as u32,
2491	HashMap::new(),
2492	);
2493	txt.insert(&mut txn, "👯❤️❤️🙇‍♀️🙇‍♀️⏰".len() as u32, "⏰");
2494	txt.format(
2495	&mut txn,
2496	"👯❤️❤️🙇‍♀️🙇‍♀️⏰⏰".len() as u32,
2497	"👩‍❤️‍💋‍👨".len() as u32,
2498	HashMap::new(),
2499	);
2500	txt.remove_range(
2501	&mut txn,
2502	"👯❤️❤️🙇‍♀️🙇‍♀️⏰⏰👩‍❤️‍💋‍👩".len() as u32,
2503	"👩‍❤️‍💋‍👨".len() as u32,
2504	);
2505	assert_eq!(txt.get_string(&txn).as_str(), "👯❤️❤️🙇‍♀️🙇‍♀️⏰⏰👩‍❤️‍💋‍👨");
2506	}
2507
2508	#[test]
2509	fn insert_string_with_no_attribute() {
2510	let doc = Doc::new();
2511	let txt = doc.get_or_insert_text("test");
2512	let mut txn = doc.transact_mut();
2513
2514	let attrs = Attrs::from([("a".into(), "a".into())]);
2515	txt.insert_with_attributes(&mut txn, 0, "ac", attrs.clone());
2516	txt.insert_with_attributes(&mut txn, 1, "b", Attrs::new());
2517
2518	let expect = vec![
2519	Diff::new("a".into(), Some(Box::new(attrs.clone()))),
2520	Diff::new("b".into(), None),
2521	Diff::new("c".into(), Some(Box::new(attrs.clone()))),
2522	];
2523
2524	assert!(txt.diff(&mut txn, YChange::identity).eq(&expect))
2525	}
2526
2527	#[test]
2528	fn insert_empty_string_with_attributes() {
2529	let doc = Doc::new();
2530	let txt = doc.get_or_insert_text("test");
2531	let mut txn = doc.transact_mut();
2532
2533	let attrs = Attrs::from([("a".into(), "a".into())]);
2534	txt.insert(&mut txn, 0, "abc");
2535	txt.insert(&mut txn, 1, ""); // nothing changes
2536	txt.insert_with_attributes(&mut txn, 1, "", attrs); // nothing changes
2537
2538	assert_eq!(txt.get_string(&txn).as_str(), "abc");
2539
2540	let bin = txn.encode_state_as_update_v1(&StateVector::default());
2541
2542	let doc = Doc::new();
2543	let txt = doc.get_or_insert_text("test");
2544	let mut txn = doc.transact_mut();
2545	let update = Update::decode_v1(bin.as_slice()).unwrap();
2546	txn.apply_update(update).unwrap();
2547
2548	assert_eq!(txt.get_string(&txn).as_str(), "abc");
2549	}
2550
2551	#[test]
2552	fn snapshots() {
2553	let doc = Doc::with_client_id(1);
2554	let text = doc.get_or_insert_text("text");
2555	text.insert(&mut doc.transact_mut(), 0, "hello");
2556	let prev = doc.transact_mut().snapshot();
2557	text.insert(&mut doc.transact_mut(), 5, " world");
2558	let next = doc.transact_mut().snapshot();
2559	let diff = text.diff_range(
2560	&mut doc.transact_mut(),
2561	Some(&next),
2562	Some(&prev),
2563	YChange::identity,
2564	);
2565
2566	assert_eq!(
2567	diff,
2568	vec![
2569	Diff::new("hello".into(), None),
2570	Diff::with_change(
2571	" world".into(),
2572	None,
2573	Some(YChange::new(ChangeKind::Added, ID::new(1, 5)))
2574	)
2575	]
2576	)
2577	}
2578
2579	#[test]
2580	fn diff_with_embedded_items() {
2581	let doc = Doc::new();
2582	let text = doc.get_or_insert_text("article");
2583	let mut txn = doc.transact_mut();
2584
2585	let bold = Attrs::from([("b".into(), true.into())]);
2586	let italic = Attrs::from([("i".into(), true.into())]);
2587
2588	text.insert_with_attributes(&mut txn, 0, "hello world", italic.clone()); // "<i>hello world</i>"
2589	text.format(&mut txn, 6, 5, bold.clone()); // "<i>hello <b>world</b></i>"
2590	let image = vec![0, 0, 0, 0];
2591	text.insert_embed(&mut txn, 5, image.clone()); // insert binary after "hello"
2592	let array = text.insert_embed(&mut txn, 5, ArrayPrelim::default()); // insert array ref after "hello"
2593
2594	let italic_and_bold = Attrs::from([("b".into(), true.into()), ("i".into(), true.into())]);
2595	let chunks = text.diff(&txn, YChange::identity);
2596	assert_eq!(
2597	chunks,
2598	vec![
2599	Diff::new("hello".into(), Some(Box::new(italic.clone()))),
2600	Diff::new(Out::YArray(array), Some(Box::new(italic.clone()))),
2601	Diff::new(image.into(), Some(Box::new(italic.clone()))),
2602	Diff::new(" ".into(), Some(Box::new(italic))),
2603	Diff::new("world".into(), Some(Box::new(italic_and_bold))),
2604	]
2605	);
2606	}
2607
2608	#[test]
2609	fn multi_threading() {
2610	use std::sync::{Arc, RwLock};
2611	use std::thread::{sleep, spawn};
2612
2613	let doc = Arc::new(RwLock::new(Doc::with_client_id(1)));
2614
2615	let d2 = doc.clone();
2616	let h2 = spawn(move || {
2617	for _ in 0..10 {
2618	let millis = fastrand::u64(1..20);
2619	sleep(Duration::from_millis(millis));
2620
2621	let doc = d2.write().unwrap();
2622	let txt = doc.get_or_insert_text("test");
2623	let mut txn = doc.transact_mut();
2624	txt.push(&mut txn, "a");
2625	}
2626	});
2627
2628	let d3 = doc.clone();
2629	let h3 = spawn(move || {
2630	for _ in 0..10 {
2631	let millis = fastrand::u64(1..20);
2632	sleep(Duration::from_millis(millis));
2633
2634	let doc = d3.write().unwrap();
2635	let txt = doc.get_or_insert_text("test");
2636	let mut txn = doc.transact_mut();
2637	txt.push(&mut txn, "b");
2638	}
2639	});
2640
2641	h3.join().unwrap();
2642	h2.join().unwrap();
2643
2644	let doc = doc.read().unwrap();
2645	let txt = doc.get_or_insert_text("test");
2646	let len = txt.len(&doc.transact());
2647	assert_eq!(len, 20);
2648	}
2649
2650	#[test]
2651	fn multiline_format() {
2652	let doc = Doc::with_client_id(1);
2653	let mut txn = doc.transact_mut();
2654	let txt = txn.get_or_insert_text("text");
2655	let bold: Option<Box<Attrs>> = Some(Box::new(Attrs::from([("bold".into(), true.into())])));
2656	txt.insert(&mut txn, 0, "Test\nMulti-line\nFormatting");
2657	txt.apply_delta(
2658	&mut txn,
2659	[
2660	Delta::Retain(4, bold.clone()),
2661	Delta::retain(1), // newline character
2662	Delta::Retain(10, bold.clone()),
2663	Delta::retain(1), // newline character
2664	Delta::Retain(10, bold.clone()),
2665	],
2666	);
2667	let delta = txt.diff(&txn, YChange::identity);
2668	assert_eq!(
2669	delta,
2670	vec![
2671	Diff::new("Test".into(), bold.clone()),
2672	Diff::new("\n".into(), None),
2673	Diff::new("Multi-line".into(), bold.clone()),
2674	Diff::new("\n".into(), None),
2675	Diff::new("Formatting".into(), bold),
2676	]
2677	);
2678	}
2679
2680	#[test]
2681	fn delta_with_embeds() {
2682	let doc = Doc::with_client_id(1);
2683	let mut txn = doc.transact_mut();
2684	let txt = txn.get_or_insert_text("text");
2685	let linebreak = any!({
2686	"linebreak": "s"
2687	});
2688	txt.apply_delta(&mut txn, [Delta::insert(linebreak.clone())]);
2689	let delta = txt.diff(&txn, YChange::identity);
2690	assert_eq!(delta, vec![Diff::new(linebreak.into(), None)]);
2691	}
2692
2693	#[test]
2694	fn delta_with_shared_ref() {
2695	let d1 = Doc::with_client_id(1);
2696	let mut txn1 = d1.transact_mut();
2697	let txt1 = txn1.get_or_insert_text("text");
2698	txt1.apply_delta(
2699	&mut txn1,
2700	[Delta::insert(MapPrelim::from([("key", "val")]))],
2701	);
2702	let delta = txt1.diff(&txn1, YChange::identity);
2703	let d: MapRef = delta[0].insert.clone().cast().unwrap();
2704	assert_eq!(d.get(&txn1, "key").unwrap(), Out::Any("val".into()));
2705
2706	let triggered = Arc::new(AtomicBool::new(false));
2707	let _sub = {
2708	let triggered = triggered.clone();
2709	txt1.observe(move |txn, e| {
2710	let delta = e.delta(txn).to_vec();
2711	let d: MapRef = match &delta[0] {
2712	Delta::Inserted(insert, _) => insert.clone().cast().unwrap(),
2713	_ => unreachable!("unexpected delta"),
2714	};
2715	assert_eq!(d.get(txn, "key").unwrap(), Out::Any("val".into()));
2716	triggered.store(true, Ordering::Relaxed);
2717	})
2718	};
2719
2720	let d2 = Doc::with_client_id(2);
2721	let mut txn2 = d2.transact_mut();
2722	let txt2 = txn2.get_or_insert_text("text");
2723	let update = Update::decode_v1(&txn1.encode_update_v1()).unwrap();
2724	txn2.apply_update(update).unwrap();
2725	drop(txn1);
2726	drop(txn2);
2727
2728	assert!(triggered.load(Ordering::Relaxed), "fired event");
2729
2730	let delta = txt2.diff(&d2.transact(), YChange::identity);
2731	assert_eq!(delta.len(), 1);
2732	let d: MapRef = delta[0].insert.clone().cast().unwrap();
2733	assert_eq!(
2734	d.get(&d2.transact(), "key").unwrap(),
2735	Out::Any("val".into())
2736	);
2737	}
2738
2739	#[test]
2740	fn delta_snapshots() {
2741	let doc = Doc::with_options(Options {
2742	client_id: 1,
2743	skip_gc: true,
2744	..Default::default()
2745	});
2746	let mut txn = doc.transact_mut();
2747	let txt = txn.get_or_insert_text("text");
2748	txt.apply_delta(&mut txn, [Delta::insert("abcd")]);
2749	let snapshot1 = txn.snapshot(); // 'abcd'
2750	txt.apply_delta(
2751	&mut txn,
2752	[Delta::retain(1), Delta::insert("x"), Delta::delete(1)],
2753	);
2754	let snapshot2 = txn.snapshot(); // 'axcd'
2755	txt.apply_delta(
2756	&mut txn,
2757	[
2758	Delta::retain(2), // ax^cd
2759	Delta::delete(1), // ax^d
2760	Delta::insert("x"), // axx^d
2761	Delta::delete(1), // axx^
2762	],
2763	);
2764	let state1 = txt.diff_range(&mut txn, Some(&snapshot1), None, YChange::identity);
2765	assert_eq!(state1, vec![Diff::new("abcd".into(), None)]);
2766	let state2 = txt.diff_range(&mut txn, Some(&snapshot2), None, YChange::identity);
2767	assert_eq!(state2, vec![Diff::new("axcd".into(), None)]);
2768	let state2_diff = txt.diff_range(
2769	&mut txn,
2770	Some(&snapshot2),
2771	Some(&snapshot1),
2772	YChange::identity,
2773	);
2774	assert_eq!(
2775	state2_diff,
2776	vec![
2777	Diff {
2778	insert: "a".into(),
2779	attributes: None,
2780	ychange: None
2781	},
2782	Diff {
2783	insert: "x".into(),
2784	attributes: None,
2785	ychange: Some(YChange {
2786	kind: ChangeKind::Added,
2787	id: ID {
2788	client: 1,
2789	clock: 4
2790	}
2791	})
2792	},
2793	Diff {
2794	insert: "b".into(),
2795	attributes: None,
2796	ychange: Some(YChange {
2797	kind: ChangeKind::Removed,
2798	id: ID {
2799	client: 1,
2800	clock: 1
2801	}
2802	})
2803	},
2804	Diff {
2805	insert: "cd".into(),
2806	attributes: None,
2807	ychange: None
2808	}
2809	]
2810	);
2811	}
2812
2813	#[test]
2814	fn snapshot_delete_after() {
2815	let doc = Doc::with_options(Options {
2816	client_id: 1,
2817	skip_gc: true,
2818	..Default::default()
2819	});
2820	let mut txn = doc.transact_mut();
2821	let txt = txn.get_or_insert_text("text");
2822	txt.apply_delta(&mut txn, [Delta::insert("abcd")]);
2823	let snapshot1 = txn.snapshot();
2824	txt.apply_delta(&mut txn, [Delta::retain(4), Delta::insert("e")]);
2825	let state1 = txt.diff_range(&mut txn, Some(&snapshot1), None, YChange::identity);
2826	assert_eq!(state1, vec![Diff::new("abcd".into(), None)]);
2827	}
2828
2829	#[test]
2830	fn empty_delta_chunks() {
2831	let doc = Doc::with_client_id(1);
2832	let mut txn = doc.transact_mut();
2833	let txt = txn.get_or_insert_text("text");
2834
2835	let delta = vec![
2836	Delta::insert("a"),
2837	Delta::Inserted(
2838	"".into(),
2839	Some(Box::new(Attrs::from([(
2840	Arc::from("bold"),
2841	Any::from(true),
2842	)]))),
2843	),
2844	Delta::insert("b"),
2845	];
2846
2847	txt.apply_delta(&mut txn, delta);
2848	assert_eq!(txt.get_string(&txn), "ab");
2849
2850	let bin = txn.encode_state_as_update_v1(&StateVector::default());
2851
2852	let doc2 = Doc::with_client_id(2);
2853	let mut txn = doc2.transact_mut();
2854	let txt = txn.get_or_insert_text("text");
2855
2856	let update = Update::decode_v1(bin.as_slice()).unwrap();
2857	txn.apply_update(update).unwrap();
2858	assert_eq!(txt.get_string(&txn), "ab");
2859	}
2860	}
2861