ot_rs/core/text.rs
1use super::error::OperationError;
2use super::operation::Operation;
3use std::str::Chars;
4
5/// `ops`
6/// 本质上是 `[op]` 类型， 定义了如何将一个字符串转换为另一个字符串的 `op` 序列。
7/// 注意：当 `baseLength == base.len()` 时，说明虚拟游标移动到该文本的尾部，由于 原子操作 `Operation` 定义的操作，
8/// 游标只能向后移动，所以此时，若需要进行 `Retain` 或者 `Delete`，则需要创建一个新的 `TextOperation`
9///
10/// # Example
11/// 针对字符串 `abc`，在 用户删除了 b，并在 c 会后插入了 d。
12/// ```
13/// use ot_rs::core::TextOperation;
14/// let mut ops = TextOperation::new();
15/// ops.retain(1).delete(1).retain(1).insert("d");
16/// let base = "abc";
17/// let after = "acd";
18/// assert_eq!(after, ops.apply(base).unwrap());
19/// ```
20#[derive(Debug)]
21pub struct TextOperation {
22 /// 原子操作
23 ops: Vec<Operation>,
24 /// Retain、 Delete 的长度
25 /// 在 apply(base) -> after 时，等于 len(base)
26 base_length: usize,
27 /// Retain、Insert 的长度
28 /// 在 apply(base) -> after 时，等于 len(after)
29 after_length: usize,
30}
31
32impl PartialEq for TextOperation {
33 /// # Example
34 /// ```
35 /// use ot_rs::core::TextOperation;
36 /// let mut ops1 = TextOperation::new();
37 /// let mut ops2 = TextOperation::new();
38 /// assert!(ops1 == ops2);
39 /// ops1.retain(1).delete(1).retain(1).insert("d");
40 /// assert!(ops1 != ops2);
41 /// ops2.retain(1).delete(1).retain(1).insert("d");
42 /// assert!(ops1 == ops2);
43 /// ops2.insert("1");
44 /// assert!(ops1 != ops2);
45 /// ```
46 fn eq(&self, other: &Self) -> bool {
47 if self.base_length != other.base_length {
48 return false;
49 }
50 if self.after_length != other.after_length {
51 return false;
52 }
53 if self.ops.len() != other.ops.len() {
54 return false;
55 }
56 return self
57 .ops
58 .iter()
59 .zip(&other.ops)
60 .filter(|&(a, b)| *a != *b)
61 .count()
62 == 0;
63 }
64}
65
66impl ToString for TextOperation {
67 /// # Example
68 /// ```
69 /// use ot_rs::core::TextOperation;
70 /// let mut ops = TextOperation::new();
71 /// assert_eq!("(0->0){}", ops.to_string());
72 /// ops.retain(1).delete(1).retain(1).insert("de\"");
73 /// assert_eq!(
74 /// "(3->5){retain(1).delete(1).retain(1).insert(\"de\\\"\")}",
75 /// ops.to_string()
76 /// );
77 /// ```
78 fn to_string(&self) -> String {
79 format!("({}->{}){{", self.base_length, self.after_length).to_string()
80 + &self
81 .ops
82 .iter()
83 .map(Operation::to_string)
84 .collect::<Vec<String>>()
85 .join(".")
86 + "}"
87 }
88}
89
90impl TextOperation {
91 // === 构造函数 ===
92 /// 构造函数，创建一个无操作的 TextOperation
93 /// # Example
94 /// ```
95 /// use ot_rs::core::TextOperation;
96 /// let mut ops = TextOperation::new();
97 /// assert_eq!("(0->0){}", ops.to_string());
98 /// ```
99 pub fn new() -> TextOperation {
100 return TextOperation {
101 ops: vec![],
102 base_length: 0,
103 after_length: 0,
104 };
105 }
106
107 // === 3 个 操作函数（接收 `&mut self`） ===
108
109 /// 跳过给定数量的字符
110 /// ```
111 /// use ot_rs::core::TextOperation;
112 /// let mut ops = TextOperation::new();
113 /// ops.retain(1);
114 /// assert_eq!("(1->1){retain(1)}", ops.to_string());
115 /// ops.retain(1);
116 /// assert_eq!("(2->2){retain(2)}", ops.to_string());
117 ///
118 pub fn retain(&mut self, n: usize) -> &mut TextOperation {
119 if n == 0 {
120 return self;
121 }
122 self.base_length += n;
123 self.after_length += n;
124
125 // R(x),R(y) -> R(x+y)
126 if let Some(Operation::Retain(last_n)) = self.ops.last_mut() {
127 *last_n += n;
128 } else {
129 self.ops.push(Operation::Retain(n))
130 }
131 return self;
132 }
133
134 /// 在当前位置插入一个字符串
135 /// # Example
136 /// ```
137 /// use ot_rs::core::TextOperation;
138 /// let mut ops = TextOperation::new();
139 /// ops.insert("a");
140 /// assert_eq!("(0->1){insert(\"a\")}", ops.to_string());
141 /// ops.insert("b");
142 /// // 两次连续的插入将合并
143 /// assert_eq!("(0->2){insert(\"ab\")}", ops.to_string());
144 /// ops.delete(1);
145 /// assert_eq!("(1->2){insert(\"ab\").delete(1)}", ops.to_string());
146 /// // I,D + I 将加入的 I 合并到前面的插入
147 /// ops.insert("c");
148 /// assert_eq!("(1->3){insert(\"abc\").delete(1)}", ops.to_string());
149 /// ops.retain(1).delete(1);
150 /// assert_eq!(
151 /// "(3->4){insert(\"abc\").delete(1).retain(1).delete(1)}",
152 /// ops.to_string()
153 /// );
154 /// // D + I 将变为 I,D
155 /// ops.insert("d");
156 /// assert_eq!(
157 /// "(3->5){insert(\"abc\").delete(1).retain(1).insert(\"d\").delete(1)}",
158 /// ops.to_string()
159 /// );
160 /// ```
161 pub fn insert<T: Into<String>>(&mut self, str: T) -> &mut TextOperation {
162 let str = str.into();
163 if str == "".to_string() {
164 return self;
165 }
166 self.after_length += str.chars().count();
167 match self.ops.split_last_mut() {
168 // 合并 I(x),I(y) -> I(x+y)
169 Some((Operation::Insert(last_str), _)) => last_str.push_str(str.as_str()),
170 Some((Operation::Delete(_), op_heads)) => {
171 // 始终保持 insert 在 delete 前面
172 match op_heads.last_mut() {
173 // 合并 I(s),D(x),I(y) -> I(s+y),D(x)
174 Some(Operation::Insert(last_str)) => last_str.push_str(str.as_str()),
175 // D(x),I(y) -> I(y),D(x)
176 // 参考实现没有 bug，第一步 `ops[ops.length] = ops[ops.length-1]` 相当于插入了一个元素 😂，本质上就是上面的说明
177 // https://github.com/Operational-Transformation/ot.js/blob/e9a3a0e214dd6c001e25515274bae0842a8415f2/lib/text-operation.js#L102
178 _ => {
179 let last_delete = self.ops.last().unwrap().clone();
180 *self.ops.last_mut().unwrap() = Operation::Insert(str);
181 self.ops.push(last_delete);
182 }
183 }
184 }
185 _ => self.ops.push(Operation::Insert(str)),
186 }
187 return self;
188 }
189
190 /// 删除当前位置的字符串
191 /// # Example
192 /// ```
193 /// use ot_rs::core::TextOperation;
194 /// let mut ops = TextOperation::new();
195 /// ops.delete(1);
196 /// assert_eq!("(1->0){delete(1)}", ops.to_string());
197 /// ops.delete(2);
198 /// assert_eq!("(3->0){delete(3)}", ops.to_string());
199 /// ```
200 pub fn delete(&mut self, n: usize) -> &mut TextOperation {
201 if n == 0 {
202 return self;
203 }
204 self.base_length += n;
205
206 // D(x),D(y) -> D(x+y)
207 if let Some(Operation::Delete(last_n)) = self.ops.last_mut() {
208 *last_n += n;
209 } else {
210 self.ops.push(Operation::Delete(n))
211 }
212 return self;
213 }
214
215 /// 测试该操作 apply 后是否不产生影响
216 /// # Example
217 /// ```
218 /// use ot_rs::core::TextOperation;
219 /// let mut ops = TextOperation::new();
220 /// assert!(ops.is_noop());
221 /// ops.retain(10);
222 /// assert!(ops.is_noop());
223 /// ```
224 pub fn is_noop(&self) -> bool {
225 match self.ops.len() {
226 0 => true,
227 1 => match self.ops.first() {
228 Some(&Operation::Retain(_)) => true,
229 _ => false,
230 },
231 _ => false,
232 }
233 }
234
235 /// 将 操作 apply 应用到 base 字符串中，并返回一个新字符串；
236 /// 如果输入的字符串和操作之间不匹配，抛出一个错误。
237 /// # Example
238 /// ```
239 /// use ot_rs::core::{OperationError, TextOperation};
240 /// // 正常情况
241 /// let mut ops = TextOperation::new();
242 /// ops.retain(1).delete(1).retain(1).insert("d");
243 /// let base = "abc";
244 /// let after = "acd";
245 /// assert_eq!(after, ops.apply(base).unwrap());
246 /// // 异常情况
247 /// let mut ops = TextOperation::new();
248 /// assert_eq!(
249 /// OperationError::OperationApplyStringNotCompatible,
250 /// ops.insert("a").apply("---").unwrap_err()
251 /// );
252 /// ```
253 pub fn apply<T: Into<String>>(&self, base: T) -> Result<String, OperationError> {
254 let base = base.into();
255 let base_len = base.chars().count();
256 if base_len != self.base_length {
257 return Err(OperationError::OperationApplyStringNotCompatible);
258 }
259
260 let base_chars = &mut base.chars(); // 这是一个迭代器，不能使用切片语法，因为字符串是 utf8
261 let mut buffer: Vec<String> = Vec::with_capacity(self.ops.len());
262 let mut cursor = 0usize;
263 for op in &self.ops {
264 match op {
265 &Operation::Retain(n) => {
266 if cursor + n > base_len {
267 return Err(OperationError::OperationMoreLeftString);
268 }
269 // 遍历迭代器返回 base 前 n 个字符
270 buffer.push(chars_take(base_chars, n));
271 cursor += n // 游标移动
272 }
273 Operation::Insert(v) => buffer.push(v.clone()),
274 &Operation::Delete(n) => {
275 if cursor + n > base_len {
276 return Err(OperationError::OperationMoreLeftString);
277 }
278 cursor += n;
279 // 遍历迭代器，skip 字符
280 chars_skip(base_chars, n);
281 }
282 }
283 }
284 // 不可能发生
285 // if cursor != base_len {
286 // return Err(OperationError::OperationNotCoverWholeString);
287 // }
288 return Ok(buffer.join(""));
289 }
290
291 /// 生成 该 Operation 的 逆操作，即求 ops' 且满足 `apply(apply(s, ops), ops') = s`。可以用来实现 undo
292 /// # Example
293 /// ```
294 /// use ot_rs::core::TextOperation;
295 /// let base = "abc";
296 ///
297 /// let mut ops = TextOperation::new();
298 /// ops.retain(1).delete(1).retain(1).insert("d");
299 /// assert_eq!(
300 /// base,
301 /// ops.invert(base)
302 /// .unwrap()
303 /// .apply(ops.apply(base).unwrap())
304 /// .unwrap()
305 /// );
306 /// ```
307 pub fn invert<T: Into<String>>(&self, base: T) -> Result<TextOperation, OperationError> {
308 let base = base.into();
309 let base_len = base.chars().count();
310 if base_len != self.base_length {
311 return Err(OperationError::OperationApplyStringNotCompatible);
312 }
313
314 let base_chars = &mut base.chars(); // 这是一个迭代器，不能使用切片语法，因为字符串是 utf8
315 let mut cursor = 0usize;
316 let mut inverse = TextOperation::new();
317 // abe
318 // R1, D1, Icd, D1,
319 // acd
320 // R1, Ib, D2, Ie
321 // abe
322 for op in &self.ops {
323 match op {
324 &Operation::Retain(n) => {
325 if cursor + n > base_len {
326 return Err(OperationError::OperationMoreLeftString);
327 }
328 inverse.retain(n);
329 cursor += n;
330 chars_skip(base_chars, n);
331 }
332 Operation::Insert(str) => {
333 inverse.delete(str.chars().count());
334 }
335 &Operation::Delete(n) => {
336 if cursor + n > base_len {
337 return Err(OperationError::OperationMoreLeftString);
338 }
339 inverse.insert(chars_take(base_chars, n));
340 cursor += n;
341 }
342 }
343 }
344 // 不可能发生
345 // if cursor != base_len {
346 // return Err(OperationError::OperationNotCoverWholeString);
347 // }
348 return Ok(inverse);
349 }
350
351 /// 合并连续的两个 文本操作，满足 `apply(apply(S, A), B) = apply(S, compose(A, B))`
352 /// # Example
353 /// ```
354 /// use ot_rs::core::TextOperation;
355 /// let base = "abc";
356 /// let mut ops1 = TextOperation::new();
357 /// ops1.retain(1).insert("123").delete(1).retain(1);
358 /// let after1 = ops1.apply(base).unwrap();
359 /// assert_eq!("a123c", after1);
360 ///
361 /// let mut ops2 = TextOperation::new();
362 /// ops2.retain(2)
363 /// .insert("$$$")
364 /// .delete(1)
365 /// .retain(1)
366 /// .insert("###")
367 /// .retain(1);
368 /// let after2 = ops2.apply(&after1).unwrap();
369 ///
370 /// assert_eq!("a1$$$3###c", after2);
371 /// let compose_ops = ops1.compose(&ops2).unwrap();
372 /// assert_eq!(after2, compose_ops.apply(base).unwrap());
373 /// ```
374 pub fn compose(&self, operation2: &TextOperation) -> Result<TextOperation, OperationError> {
375 if self.after_length != operation2.base_length {
376 return Err(OperationError::SecondBaseLengthNotEqualFirstAfterLength);
377 }
378
379 let mut ops1 = self.ops.split_first();
380 let mut ops2 = operation2.ops.split_first();
381 let mut tmp: Box<Operation>; // 修复 rust 生命周期检测
382
383 let mut composed = TextOperation::new();
384 // 思路大概是：
385 // 设置两个游标，同时遍历 ops1，ops2；
386 // 每一轮迭代，都相当于重新调用了 compose，是一个递归过程；
387 // 定义递归函数 compose(ops1, ops2, ops3) 将 ops1、ops2 合并成 ops3
388 // 因此我们只需按照递归的思路，思考初始的状态的9种组合即可
389 // 1. compose([R(x), ..ops1], [R(y), ..ops2], [])
390 // x == y: compose(ops1, ops2, [R(x)])
391 // x > y : compose([R(x-y), ..ops1], ops2, [R(y)])
392 // x < y : compose(ops1, [R(y-x), ..ops2], [R(y)])
393 // 2. compose([R(x), ..ops1], [I(y), ..ops2], [])
394 // : compose([R(x), ..ops1], ops2, [I(y)])
395 // 3. compose([R(x), ..ops1], [D(y), ..ops2], [])
396 // y < x : compose([R(x-y), ..ops1], ops2, [D(y)])
397 // y = x: compose(ops1, ops2, [D(y)])
398 // y > x : compose(ops1, [D(y-x) ,..ops2], [D(x)])
399 // 4. compose([I(x), ..ops1], [R(y), ..ops2], [])
400 // ...
401 // 在此就不全部枚举了，本质上就 op1、op2 将范围大的那个拆一部分出来，然后继续递归
402 // 将以上全部枚举出来后，进行剪枝，并转化为迭代的形式，就可以得到如下的算法
403 loop {
404 match (ops1, ops2) {
405 // None, None
406 (None, None) => break,
407 // D, _
408 (Some((&Operation::Delete(n1), ops_tail1)), _) => {
409 composed.delete(n1);
410 ops1 = ops_tail1.split_first();
411 continue;
412 }
413 // _, I
414 (_, Some((Operation::Insert(s), ops_tail))) => {
415 composed.insert(s.clone());
416 ops2 = ops_tail.split_first();
417 continue;
418 }
419 // None, _
420 (None, _) => return Err(OperationError::ComposeFirstTooShort),
421 // _, None
422 (_, None) => return Err(OperationError::ComposeFirstTooLong),
423 (
424 Some((&Operation::Retain(n1), ops_tail1)),
425 Some((&Operation::Retain(n2), ops_tail2)),
426 ) => {
427 if n1 > n2 {
428 composed.retain(n2);
429 tmp = Box::new(Operation::Retain(n1 - n2));
430 ops1 = Some((&tmp, ops_tail1));
431 ops2 = ops_tail2.split_first();
432 } else if n1 == n2 {
433 composed.retain(n1);
434 ops1 = ops_tail1.split_first();
435 ops2 = ops_tail2.split_first();
436 } else {
437 composed.retain(n1);
438 tmp = Box::new(Operation::Retain(n2 - n1));
439 ops2 = Some((&tmp, ops_tail2));
440 ops1 = ops_tail1.split_first();
441 }
442 }
443 // I, D
444 (
445 Some((Operation::Insert(s1), ops_tail1)),
446 Some((&Operation::Delete(n2), ops_tail2)),
447 ) => {
448 let l1 = s1.chars().count();
449 if l1 > n2 {
450 tmp = Box::new(Operation::Insert(chars_tail(&mut s1.chars(), n2)));
451 ops1 = Some((&tmp, ops_tail1));
452 ops2 = ops_tail2.split_first();
453 } else if l1 == n2 {
454 ops1 = ops_tail1.split_first();
455 ops2 = ops_tail2.split_first();
456 } else {
457 tmp = Box::new(Operation::Delete(n2 - l1));
458 ops1 = ops_tail1.split_first();
459 ops2 = Some((&tmp, ops_tail2));
460 }
461 }
462 // I,R
463 (
464 Some((Operation::Insert(s1), ops_tail1)),
465 Some((&Operation::Retain(n2), ops_tail2)),
466 ) => {
467 let l1 = s1.chars().count();
468 if l1 > n2 {
469 let chars = &mut s1.chars();
470 composed.insert(chars_take(chars, n2));
471 tmp = Box::new(Operation::Insert(chars_take(chars, l1 - n2)));
472 ops1 = Some((&tmp, ops_tail1));
473 ops2 = ops_tail2.split_first();
474 } else if l1 == n2 {
475 composed.insert(s1.clone());
476 ops1 = ops_tail1.split_first();
477 ops2 = ops_tail2.split_first();
478 } else {
479 composed.insert(s1.clone());
480 tmp = Box::new(Operation::Retain(n2 - l1));
481 ops2 = Some((&tmp, ops_tail2));
482 ops1 = ops_tail1.split_first();
483 }
484 }
485 // R,D
486 (
487 Some((&Operation::Retain(n1), ops_tail1)),
488 Some((&Operation::Delete(n2), ops_tail2)),
489 ) => {
490 if n1 > n2 {
491 composed.delete(n2);
492 tmp = Box::new(Operation::Retain(n1 - n2));
493 ops1 = Some((&tmp, ops_tail1));
494 ops2 = ops_tail2.split_first();
495 } else if n1 == n2 {
496 composed.delete(n2);
497 ops1 = ops_tail1.split_first();
498 ops2 = ops_tail2.split_first();
499 } else {
500 composed.delete(n1);
501 tmp = Box::new(Operation::Delete(n2 - n1));
502 ops2 = Some((&tmp, ops_tail2));
503 ops1 = ops_tail1.split_first();
504 }
505 }
506 }
507 }
508 Ok(composed)
509 }
510
511 /// 获取起始游标
512 fn first_cursor(&self) -> usize {
513 if let Some(&Operation::Retain(n)) = self.ops.first() {
514 return n;
515 }
516 return 0;
517 }
518
519 /// 如果当前操作是简单操作，则返回这个简单操作的内容，否者返回 None。
520 /// 简单操作指的是：只进行了一次或零次 Insert/Delete 操作
521 fn get_simple_operation(&self) -> Option<&Operation> {
522 match self.ops.as_slice() {
523 // [_] => [0]
524 [first] => Some(first),
525 // [R, _] => [1]
526 [Operation::Retain(_), second] => Some(second),
527 // [I|D, R] => [0]
528 [first, Operation::Retain(_)] => Some(first),
529 // [R, _, R] => [1]
530 [Operation::Retain(_), second, Operation::Retain(_)] => Some(second),
531 _ => None,
532 }
533 }
534
535 /// 当使用 ctrl-z 撤消最近的更改时，希望程序不会撤消每一次击键，而是撤消一口气写下的最后一句话或通过按住退格键所做的删除。
536 /// 这可以通过在将撤消栈上的操作进行 compose 来实现。 这个方法可以帮助决定是否应该组合两个操作。
537 /// 如果操作是 `连续的插入操作` 或 `连续的删除操作`，则返回 true。
538 /// 可能希望包括其他因素，例如自上次更改决定以来的时间。
539 /// # Example
540 /// ```
541 /// use ot_rs::core::TextOperation;
542 /// let mut ops1: TextOperation;
543 /// let mut ops2: TextOperation;
544 /// // noop;I / I;noop
545 /// ops1 = TextOperation::new();
546 /// ops1.retain(3);
547 /// ops2 = TextOperation::new();
548 /// ops2.retain(1).insert("xxx").retain(2);
549 /// assert!(ops1.should_be_composed_with(&ops2));
550 /// assert!(ops2.should_be_composed_with(&ops1));
551 /// // I;I 正常输入
552 /// ops1 = TextOperation::new();
553 /// ops1.retain(1).insert("a").retain(2);
554 /// ops2 = TextOperation::new();
555 /// ops2.retain(2).insert("b").retain(2);
556 /// assert!(ops1.should_be_composed_with(&ops2));
557 /// ops1.delete(3);
558 /// assert!(!ops1.should_be_composed_with(&ops2));
559 /// // I;I 插入后光标发生变化
560 /// ops1 = TextOperation::new();
561 /// ops1.retain(1).insert("b").retain(2);
562 /// ops2 = TextOperation::new();
563 /// ops2.retain(1).insert("a").retain(3);
564 /// assert!(!ops1.should_be_composed_with(&ops2));
565 /// // D;D 退格键方式
566 /// ops1 = TextOperation::new();
567 /// ops1.retain(4).delete(3).retain(10);
568 /// ops2 = TextOperation::new();
569 /// ops2.retain(2).delete(2).retain(10);
570 /// assert!(ops1.should_be_composed_with(&ops2));
571 /// // D;D delete键方式
572 /// ops2 = TextOperation::new();
573 /// ops2.retain(4).delete(7).retain(3);
574 /// assert!(ops1.should_be_composed_with(&ops2));
575 /// // D;D 不连续的删除
576 /// ops2 = TextOperation::new();
577 /// ops2.retain(2).delete(9).retain(3);
578 /// assert!(!ops1.should_be_composed_with(&ops2));
579 /// ```
580 pub fn should_be_composed_with(&self, other: &TextOperation) -> bool {
581 // 无影响的操作，可以合并
582 if self.is_noop() || other.is_noop() {
583 return true;
584 }
585 let (a_first_cursor, b_first_cursor) = (self.first_cursor(), other.first_cursor());
586 let (a_sample, b_sample) = (self.get_simple_operation(), other.get_simple_operation());
587 // 只要一个是非简单操作，则不可以合并
588 if a_sample.is_none() || b_sample.is_none() {
589 return false;
590 }
591 match (a_sample, b_sample, a_first_cursor, b_first_cursor) {
592 // I, I - 保证后插入的在之前插入的后方进行插入
593 (Some(Operation::Insert(str)), Some(Operation::Insert(_)), _, _) => {
594 return str.chars().count() + a_first_cursor == b_first_cursor; // 连续输入两个字符
595 }
596 // D, D
597 (Some(&Operation::Delete(_)), Some(&Operation::Delete(dn2)), _, _) => {
598 return b_first_cursor as i64 + dn2 as i64 == a_first_cursor as i64 // 按两下退格的场景
599 || a_first_cursor == b_first_cursor; // 按两下 delete 键的场景
600 }
601 // 其他情况
602 _ => false,
603 }
604 }
605
606 /// 决定两个操作如果被 invert 是否应该相互组合，即 `should_be_composed_with_inverted(a, b) = should_be_composed_with_inverted(b^{-1}, a^{-1})`
607 pub fn should_be_composed_with_inverted(&self, other: &TextOperation) -> bool {
608 // 无影响的操作，可以合并
609 if self.is_noop() || other.is_noop() {
610 return true;
611 }
612 let (a_first_cursor, b_first_cursor) = (self.first_cursor(), other.first_cursor());
613 let (a_sample, b_sample) = (self.get_simple_operation(), other.get_simple_operation());
614 // 只要一个是非简单操作，则不可以合并
615 if a_sample.is_none() || b_sample.is_none() {
616 return false;
617 }
618 match (a_sample, b_sample, a_first_cursor, b_first_cursor) {
619 // I, I - 因为是逆，所以原操作是 Delete
620 (Some(Operation::Insert(str)), Some(Operation::Insert(_)), _, _) => {
621 return a_first_cursor + str.chars().count() == b_first_cursor
622 || a_first_cursor == b_first_cursor;
623 }
624 // D, D - 因为是逆，所以原操作是 Insert
625 (Some(&Operation::Delete(_)), Some(&Operation::Delete(dn2)), _, _) => {
626 return b_first_cursor as i64 - dn2 as i64 == a_first_cursor as i64
627 }
628 // 其他情况
629 _ => false,
630 }
631 }
632
633 /// 这个函数是 OT 算法的核心。
634 /// 转换两个基于同一版本 S 的操作 A 和 B，返回 A' 和 B'，使其满足
635 /// `apply(apply(S, A), B') = apply(apply(S, B), A')`。
636 pub fn transform(
637 &self,
638 operation2: &TextOperation,
639 ) -> Result<(TextOperation, TextOperation), OperationError> {
640 let operation1 = self;
641 if operation1.base_length != operation2.base_length {
642 return Err(OperationError::TransformBaseDifferent);
643 }
644
645 let mut tmp: Box<Operation>; // 修复 rust 生命周期检测
646 let (mut operation1prime, mut operation2prime) =
647 (TextOperation::new(), TextOperation::new());
648
649 let mut ops1 = self.ops.split_first();
650 let mut ops2 = operation2.ops.split_first();
651 // 和 compose 方法类似
652 // 思路大概是：
653 // 设置两个游标，同时遍历 ops1，ops2；
654 // 每一轮迭代，都要保证游标，在 S 的位置是一致的
655 // 因此我们只需按照递归的思路，思考初始的状态的9种组合即可。
656 // 全部枚举出来后，进行剪枝，就可以得到如下的算法
657 loop {
658 match (ops1, ops2) {
659 (None, None) => break,
660 // 如下两种情况：只要有一方是 Insert，这一方面方的 Prime 就跳过，量一方的 Prime 就插入
661 // (3 种情况) I, _
662 (Some((Operation::Insert(str1), tail1)), _) => {
663 operation1prime.insert(str1.clone());
664 operation2prime.retain(str1.chars().count());
665 ops1 = tail1.split_first();
666 }
667 // (2 种情况) _, I
668 (_, Some((Operation::Insert(str2), tail2))) => {
669 operation1prime.retain(str2.chars().count());
670 operation2prime.insert(str2.clone());
671 ops2 = tail2.split_first();
672 }
673 // 异常：只要有一方完成另一方未完成，则报错
674 (None, _) => return Err(OperationError::ComposeFirstTooShort),
675 (_, None) => return Err(OperationError::ComposeFirstTooLong),
676 // (1 种情况) R, R
677 (Some((&Operation::Retain(n1), tail1)), Some((&Operation::Retain(n2), tail2))) => {
678 let min_n = if n1 > n2 {
679 tmp = Box::new(Operation::Retain(n1 - n2));
680 ops1 = Some((&tmp, tail1));
681 ops2 = tail2.split_first();
682 n2
683 } else if n1 == n2 {
684 ops1 = tail1.split_first();
685 ops2 = tail2.split_first();
686 n2
687 } else {
688 tmp = Box::new(Operation::Retain(n2 - n1));
689 ops1 = tail1.split_first();
690 ops2 = Some((&tmp, tail2));
691 n1
692 };
693 operation1prime.retain(min_n);
694 operation2prime.retain(min_n);
695 }
696 // (1 种情况) D, D
697 // 同时删除，我们只需要将删除长的保留后面部分，删除短的直接跳过
698 (Some((&Operation::Delete(n1), tail1)), Some((&Operation::Delete(n2), tail2))) => {
699 if n1 > n2 {
700 tmp = Box::new(Operation::Delete(n1 - n2));
701 ops1 = Some((&tmp, tail1));
702 ops2 = tail2.split_first();
703 } else if n1 == n2 {
704 ops1 = tail1.split_first();
705 ops2 = tail2.split_first();
706 } else {
707 tmp = Box::new(Operation::Delete(n2 - n1));
708 ops1 = tail1.split_first();
709 ops2 = Some((&tmp, tail2));
710 }
711 }
712 // 接下来两种情况是 D,R 和 R,D
713 // (1 种情况) D, R
714 (Some((&Operation::Delete(n1), tail1)), Some((&Operation::Retain(n2), tail2))) => {
715 let min_n = if n1 > n2 {
716 tmp = Box::new(Operation::Delete(n1 - n2));
717 ops1 = Some((&tmp, tail1));
718 ops2 = tail2.split_first();
719 n2
720 } else if n1 == n2 {
721 ops1 = tail1.split_first();
722 ops2 = tail2.split_first();
723 n2
724 } else {
725 tmp = Box::new(Operation::Retain(n2 - n1));
726 ops1 = tail1.split_first();
727 ops2 = Some((&tmp, tail2));
728 n1
729 };
730 operation1prime.delete(min_n);
731 }
732 // (1 种情况) R, D
733 (Some((&Operation::Retain(n1), tail1)), Some((&Operation::Delete(n2), tail2))) => {
734 let min_n = if n1 > n2 {
735 tmp = Box::new(Operation::Retain(n1 - n2));
736 ops1 = Some((&tmp, tail1));
737 ops2 = tail2.split_first();
738 n2
739 } else if n1 == n2 {
740 ops1 = tail1.split_first();
741 ops2 = tail2.split_first();
742 n2
743 } else {
744 tmp = Box::new(Operation::Delete(n2 - n1));
745 ops1 = tail1.split_first();
746 ops2 = Some((&tmp, tail2));
747 n1
748 };
749 operation2prime.delete(min_n);
750 } // _ => return Err(OperationError::TransformNotCompatible),
751 }
752 }
753 return Ok((operation1prime, operation2prime));
754 }
755}
756
757impl Default for TextOperation {
758 fn default() -> Self {
759 Self::new()
760 }
761}
762
763fn chars_take(chars: &mut Chars, n: usize) -> String {
764 (0..n).map(|_| chars.next().unwrap()).collect::<String>()
765}
766
767fn chars_tail(chars: &mut Chars, skip: usize) -> String {
768 chars_skip(chars, skip);
769 chars.collect::<String>()
770}
771
772fn chars_skip(chars: &mut Chars, n: usize) {
773 (0..n).for_each(|_| {
774 chars.next().unwrap();
775 })
776}
777
778#[cfg(test)]
779mod tests {
780
781 use crate::core::operation::Operation;
782
783 use super::TextOperation;
784 use rand::{self, Rng};
785
786 const CHARSET: [char; 10] = ['a', 'b', 'c', '1', '2', '3', '中', '文', '😄', '😂'];
787 // const RAND_TEST_COUNT: usize = 500;
788 const RAND_TEST_COUNT: usize = 100;
789
790 fn random_string(n: usize) -> String {
791 let mut rng: rand::prelude::ThreadRng = rand::thread_rng();
792 (0..n)
793 .map(|_| rng.gen_range(0..CHARSET.len()))
794 .map(|i| CHARSET[i])
795 .collect()
796 }
797
798 fn random_operation<T: Into<String>>(base: T) -> TextOperation {
799 let base = base.into();
800 let mut ops = TextOperation::new();
801 let mut rng: rand::prelude::ThreadRng = rand::thread_rng();
802 loop {
803 let left = base.chars().count() - ops.base_length;
804 if left == 0 {
805 break;
806 }
807 let r = rng.gen_range(0.0..1.0);
808 let l = rng.gen_range(1..=left);
809 if r < 0.2 {
810 ops.insert(random_string(l));
811 } else if r < 0.4 {
812 ops.delete(l);
813 } else {
814 ops.retain(l);
815 }
816 }
817 if rng.gen_range(0.0..1.0) < 0.3 {
818 ops.insert(random_string(10));
819 }
820 ops
821 }
822
823 fn run_n(n: usize, f: fn() -> ()) {
824 for _ in 0..n {
825 f();
826 }
827 }
828
829 #[test]
830 fn test_apply() {
831 run_n(RAND_TEST_COUNT, || {
832 let base = random_string(50);
833 let ops = random_operation(&base);
834 let after = ops.apply(&base).unwrap();
835 println!(" {} \n->\n {} \nby\n {}", &base, &after, ops.to_string());
836 assert_eq!(base.chars().count(), ops.base_length);
837 assert_eq!(after.chars().count(), ops.after_length);
838 })
839 }
840
841 #[test]
842 fn test_invert() {
843 run_n(RAND_TEST_COUNT, || {
844 let base = random_string(50);
845 let ops = random_operation(&base);
846 assert_eq!(
847 base,
848 ops.invert(&base)
849 .unwrap()
850 .apply(ops.apply(&base).unwrap())
851 .unwrap()
852 );
853 })
854 }
855
856 #[test]
857 fn test_compose() {
858 run_n(RAND_TEST_COUNT, || {
859 // after2 = apply(apply(base, ops1), ops2)
860 let base = random_string(50);
861 let ops1 = random_operation(&base);
862 let after1 = ops1.apply(&base).unwrap();
863 let ops2 = random_operation(&after1);
864 let after2 = ops2.apply(&after1).unwrap();
865 // ops1 + ops2 = compose_ops;
866 let compose_ops = ops1.compose(&ops2).unwrap();
867 assert_eq!(after2, compose_ops.apply(&base).unwrap());
868 })
869 }
870
871 #[test]
872 fn test_first_cursor() {
873 assert_eq!(0, TextOperation::new().first_cursor());
874 assert_eq!(0, TextOperation::new().delete(1).first_cursor());
875 assert_eq!(1, TextOperation::new().retain(1).first_cursor());
876 assert_eq!(0, TextOperation::new().insert("a").first_cursor());
877 }
878
879 #[test]
880 fn test_get_simple_operation() {
881 assert_eq!(None, TextOperation::new().get_simple_operation());
882 assert_eq!(
883 &Operation::Delete(1),
884 TextOperation::new()
885 .delete(1)
886 .get_simple_operation()
887 .unwrap()
888 );
889 assert_eq!(
890 &Operation::Retain(1),
891 TextOperation::new()
892 .retain(1)
893 .get_simple_operation()
894 .unwrap()
895 );
896 assert_eq!(
897 &Operation::Insert("abc".to_string()),
898 TextOperation::new()
899 .retain(1)
900 .insert("abc")
901 .retain(1)
902 .get_simple_operation()
903 .unwrap()
904 );
905 }
906
907 #[test]
908 fn should_be_composed_with_inverted() {
909 run_n(RAND_TEST_COUNT, || {
910 // invariant: should_be_composed_with_inverted(a, b) = should_be_composed_with_inverted(b^{-1}, a^{-1})
911 let base = random_string(50);
912 let ops1 = random_operation(&base);
913 let ops1_inverted = ops1.invert(&base).unwrap();
914 let after1 = ops1.apply(&base).unwrap();
915
916 let ops2 = random_operation(&after1);
917 let ops2_inverted = ops2.invert(&after1).unwrap();
918 assert_eq!(
919 ops1.should_be_composed_with(&ops2),
920 ops2_inverted.should_be_composed_with_inverted(&ops1_inverted),
921 );
922 })
923 }
924
925 #[test]
926 fn should_transform() {
927 // transform(a, b) => ('a, 'b)
928 // apply(apply(s, a), a') = apply(apply(s, b), a')
929 // compose(a, b') = compose(b, a')
930 run_n(RAND_TEST_COUNT, || {
931 let base = random_string(50);
932 let sa = random_operation(&base);
933 let sb = random_operation(&base);
934 let (sa_prime, sb_prime) = TextOperation::transform(&sa, &sb).unwrap();
935 let ab_prime = sa.compose(&sb_prime).unwrap();
936 let ba_prime = sb.compose(&sa_prime).unwrap();
937 let sa_sb_prime_after = ab_prime.apply(&base);
938 let sb_sa_prime_after = ba_prime.apply(&base);
939 assert_eq!(ab_prime, ba_prime);
940 assert_eq!(sa_sb_prime_after, sb_sa_prime_after);
941 });
942 }
943}