Skip to content

Commit 7e7254b

Browse files
appflowyappflowy
committed
1. fix the potential infinite loop when composing delta. Because of calculating the wrong code unit offset.
2. add test of calculating Chinese character
1 parent c456687 commit 7e7254b

File tree

12 files changed

+224
-174
lines changed

12 files changed

+224
-174
lines changed

‎frontend/rust-lib/flowy-document/tests/document/document_test.rs‎

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,19 @@ async fn document_sync_insert_test() {
4444
}
4545

4646
#[tokio::test]
47-
async fn document_sync_delete_test1() {
47+
async fn document_sync_insert_in_chinese() {
48+
let s = "好".to_owned();
49+
let offset = count_utf16_code_units(&s);
50+
let scripts = vec![
51+
InsertText("你", 0),
52+
InsertText("好", offset),
53+
AssertJson(r#"[{"insert":"你好\n"}]"#),
54+
];
55+
EditorTest::new().await.run_scripts(scripts).await;
56+
}
57+
58+
#[tokio::test]
59+
async fn document_sync_delete_in_english() {
4860
let scripts = vec![
4961
InsertText("1", 0),
5062
InsertText("2", 1),
@@ -55,6 +67,19 @@ async fn document_sync_delete_test1() {
5567
EditorTest::new().await.run_scripts(scripts).await;
5668
}
5769

70+
#[tokio::test]
71+
async fn document_sync_delete_in_chinese() {
72+
let s = "好".to_owned();
73+
let offset = count_utf16_code_units(&s);
74+
let scripts = vec![
75+
InsertText("你", 0),
76+
InsertText("好", offset),
77+
Delete(Interval::new(0, offset)),
78+
AssertJson(r#"[{"insert":"好\n"}]"#),
79+
];
80+
EditorTest::new().await.run_scripts(scripts).await;
81+
}
82+
5883
#[tokio::test]
5984
async fn document_sync_replace_test() {
6085
let scripts = vec![

‎frontend/rust-lib/flowy-document/tests/editor/attribute_test.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -727,6 +727,7 @@ fn attributes_format_emoji() {
727727
let len = s.utf16_size();
728728
assert_eq!(3, len);
729729
assert_eq!(2, s.graphemes(true).count());
730+
730731
let ops = vec![
731732
Insert(0, emoji_s, 0),
732733
AssertDocJson(0, r#"[{"insert":"👋 \n"}]"#),

‎frontend/rust-lib/flowy-document/tests/editor/op_test.rs‎

Lines changed: 51 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -184,7 +184,7 @@ fn delta_get_ops_in_interval_7() {
184184
}
185185

186186
#[test]
187-
fn delta_seek_1() {
187+
fn delta_op_seek() {
188188
let mut delta = RichTextDelta::default();
189189
let insert_a = OpBuilder::insert("12345").build();
190190
let retain_a = OpBuilder::retain(3).build();
@@ -196,74 +196,80 @@ fn delta_seek_1() {
196196
}
197197

198198
#[test]
199-
fn delta_seek_2() {
199+
fn delta_utf16_code_unit_seek() {
200200
let mut delta = RichTextDelta::default();
201201
delta.add(OpBuilder::insert("12345").build());
202202

203203
let mut iter = DeltaIter::new(&delta);
204-
assert_eq!(iter.next_op_with_len(1).unwrap(), OpBuilder::insert("1").build());
204+
iter.seek::<Utf16CodeUnitMetric>(3);
205+
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("45").build());
205206
}
206207

207208
#[test]
208-
fn delta_seek_3() {
209+
fn delta_utf16_code_unit_seek_with_attributes() {
209210
let mut delta = RichTextDelta::default();
210-
delta.add(OpBuilder::insert("12345").build());
211+
let attributes = AttributeBuilder::new()
212+
.add_attr(RichTextAttribute::Bold(true))
213+
.add_attr(RichTextAttribute::Italic(true))
214+
.build();
215+
216+
delta.add(OpBuilder::insert("1234").attributes(attributes.clone()).build());
217+
delta.add(OpBuilder::insert("\n").build());
211218

212219
let mut iter = DeltaIter::new(&delta);
213-
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("12").build());
220+
iter.seek::<Utf16CodeUnitMetric>(0);
214221

215-
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("34").build());
222+
assert_eq!(
223+
iter.next_op_with_len(4).unwrap(),
224+
OpBuilder::insert("1234").attributes(attributes).build(),
225+
);
226+
}
216227

228+
#[test]
229+
fn delta_next_op_len() {
230+
let mut delta = RichTextDelta::default();
231+
delta.add(OpBuilder::insert("12345").build());
232+
let mut iter = DeltaIter::new(&delta);
233+
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("12").build());
234+
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("34").build());
217235
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("5").build());
218-
219236
assert_eq!(iter.next_op_with_len(1), None);
220237
}
221238

222239
#[test]
223-
fn delta_seek_4() {
240+
fn delta_next_op_len_with_chinese() {
224241
let mut delta = RichTextDelta::default();
225-
delta.add(OpBuilder::insert("12345").build());
242+
delta.add(OpBuilder::insert("你好").build());
226243

227244
let mut iter = DeltaIter::new(&delta);
228-
iter.seek::<CharMetric>(3);
229-
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("45").build());
245+
assert_eq!(iter.next_op_len().unwrap(), 2);
246+
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("你好").build());
230247
}
231248

232249
#[test]
233-
fn delta_seek_5() {
250+
fn delta_next_op_len_with_english() {
234251
let mut delta = RichTextDelta::default();
235-
let attributes = AttributeBuilder::new()
236-
.add_attr(RichTextAttribute::Bold(true))
237-
.add_attr(RichTextAttribute::Italic(true))
238-
.build();
239-
240-
delta.add(OpBuilder::insert("1234").attributes(attributes.clone()).build());
241-
delta.add(OpBuilder::insert("\n").build());
242-
252+
delta.add(OpBuilder::insert("ab").build());
243253
let mut iter = DeltaIter::new(&delta);
244-
iter.seek::<CharMetric>(0);
245-
246-
assert_eq!(
247-
iter.next_op_with_len(4).unwrap(),
248-
OpBuilder::insert("1234").attributes(attributes).build(),
249-
);
254+
assert_eq!(iter.next_op_len().unwrap(), 2);
255+
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::insert("ab").build());
250256
}
251257

252258
#[test]
253-
fn delta_next_op_len_test() {
259+
fn delta_next_op_len_after_seek() {
254260
let mut delta = RichTextDelta::default();
255261
delta.add(OpBuilder::insert("12345").build());
256-
257262
let mut iter = DeltaIter::new(&delta);
258-
iter.seek::<CharMetric>(3);
263+
assert_eq!(iter.next_op_len().unwrap(), 5);
264+
iter.seek::<Utf16CodeUnitMetric>(3);
259265
assert_eq!(iter.next_op_len().unwrap(), 2);
260266
assert_eq!(iter.next_op_with_len(1).unwrap(), OpBuilder::insert("4").build());
261267
assert_eq!(iter.next_op_len().unwrap(), 1);
262268
assert_eq!(iter.next_op().unwrap(), OpBuilder::insert("5").build());
263269
}
264270

265271
#[test]
266-
fn delta_next_op_len_test2() {
272+
fn delta_next_op_len_none() {
267273
let mut delta = RichTextDelta::default();
268274
delta.add(OpBuilder::insert("12345").build());
269275
let mut iter = DeltaIter::new(&delta);
@@ -290,7 +296,7 @@ fn delta_next_op_with_len_cross_op_return_last() {
290296
delta.add(OpBuilder::insert("678").build());
291297

292298
let mut iter = DeltaIter::new(&delta);
293-
iter.seek::<CharMetric>(4);
299+
iter.seek::<Utf16CodeUnitMetric>(4);
294300
assert_eq!(iter.next_op_len().unwrap(), 1);
295301
assert_eq!(iter.next_op_with_len(2).unwrap(), OpBuilder::retain(1).build());
296302
}
@@ -475,7 +481,7 @@ fn transform_random_delta() {
475481
}
476482

477483
#[test]
478-
fn transform_with_two_delta_test() {
484+
fn transform_with_two_delta() {
479485
let mut a = RichTextDelta::default();
480486
let mut a_s = String::new();
481487
a.insert(
@@ -515,7 +521,7 @@ fn transform_with_two_delta_test() {
515521
}
516522

517523
#[test]
518-
fn transform_two_plain_delta_test() {
524+
fn transform_two_plain_delta() {
519525
let ops = vec![
520526
Insert(0, "123", 0),
521527
Insert(1, "456", 0),
@@ -527,7 +533,7 @@ fn transform_two_plain_delta_test() {
527533
}
528534

529535
#[test]
530-
fn transform_two_plain_delta_test2() {
536+
fn transform_two_plain_delta2() {
531537
let ops = vec![
532538
Insert(0, "123", 0),
533539
Insert(1, "456", 0),
@@ -721,6 +727,16 @@ fn delta_invert_attribute_delta_with_attribute_delta() {
721727
TestBuilder::new().run_scripts::<PlainDoc>(ops);
722728
}
723729

730+
#[test]
731+
fn delta_compose_str() {
732+
let ops = vec![
733+
Insert(0, "1", 0),
734+
Insert(0, "2", 1),
735+
AssertDocJson(0, r#"[{"insert":"12\n"}]"#),
736+
];
737+
TestBuilder::new().run_scripts::<NewlineDoc>(ops);
738+
}
739+
724740
#[test]
725741
#[should_panic]
726742
fn delta_compose_with_missing_delta() {

‎shared-lib/flowy-collaboration/src/document/document.rs‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -112,7 +112,6 @@ impl Document {
112112
let text = data.to_string();
113113
let interval = Interval::new(index, index);
114114
let _ = validate_interval(&self.delta, &interval)?;
115-
116115
let delta = self.view.insert(&self.delta, &text, interval)?;
117116
self.compose_delta(delta.clone())?;
118117
Ok(delta)

‎shared-lib/flowy-collaboration/src/document/extensions/delete/preserve_line_format_merge.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
use crate::{document::DeleteExt, util::is_newline};
22
use lib_ot::{
3-
core::{Attributes, CharMetric, DeltaBuilder, DeltaIter, Interval, NEW_LINE},
3+
core::{Attributes, DeltaBuilder, DeltaIter, Interval, Utf16CodeUnitMetric, NEW_LINE},
44
rich_text::{plain_attributes, RichTextDelta},
55
};
66

@@ -22,7 +22,7 @@ impl DeleteExt for PreserveLineFormatOnMerge {
2222
return None;
2323
}
2424

25-
iter.seek::<CharMetric>(interval.size() - 1);
25+
iter.seek::<Utf16CodeUnitMetric>(interval.size() - 1);
2626
let mut new_delta = DeltaBuilder::new()
2727
.retain(interval.start)
2828
.delete(interval.size())

‎shared-lib/flowy-collaboration/src/document/extensions/insert/reset_format_on_new_line.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
use crate::{document::InsertExt, util::is_newline};
22
use lib_ot::{
3-
core::{CharMetric, DeltaBuilder, DeltaIter, NEW_LINE},
3+
core::{DeltaBuilder, DeltaIter, Utf16CodeUnitMetric, NEW_LINE},
44
rich_text::{RichTextAttributeKey, RichTextAttributes, RichTextDelta},
55
};
66

@@ -14,7 +14,7 @@ impl InsertExt for ResetLineFormatOnNewLine {
1414
}
1515

1616
let mut iter = DeltaIter::new(delta);
17-
iter.seek::<CharMetric>(index);
17+
iter.seek::<Utf16CodeUnitMetric>(index);
1818
let next_op = iter.next_op()?;
1919
if !next_op.get_data().starts_with(NEW_LINE) {
2020
return None;

‎shared-lib/flowy-collaboration/src/document/view.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ impl View {
3232
for ext in &self.insert_exts {
3333
if let Some(mut delta) = ext.apply(delta, interval.size(), text, interval.start) {
3434
trim(&mut delta);
35-
tracing::debug!("[{}]: applied, delta: {}", ext.ext_name(), delta);
35+
tracing::debug!("[{}]: process delta: {}", ext.ext_name(), delta);
3636
new_delta = Some(delta);
3737
break;
3838
}

‎shared-lib/lib-ot/src/core/delta/cursor.rs‎

Lines changed: 22 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -35,13 +35,13 @@ where
3535
}
3636

3737
// get the next operation interval
38-
pub fn next_iv(&self) -> Interval { self.next_iv_before(None).unwrap_or_else(|| Interval::new(0, 0)) }
38+
pub fn next_iv(&self) -> Interval { self.next_iv_with_len(None).unwrap_or_else(|| Interval::new(0, 0)) }
3939

4040
pub fn next_op(&mut self) -> Option<Operation<T>> { self.next_with_len(None) }
4141

4242
// get the last operation before the end.
4343
// checkout the delta_next_op_with_len_cross_op_return_last test for more detail
44-
pub fn next_with_len(&mut self, force_end: Option<usize>) -> Option<Operation<T>> {
44+
pub fn next_with_len(&mut self, expected_len: Option<usize>) -> Option<Operation<T>> {
4545
let mut find_op = None;
4646
let holder = self.next_op.clone();
4747
let mut next_op = holder.as_ref();
@@ -53,7 +53,9 @@ where
5353
let mut consume_len = 0;
5454
while find_op.is_none() && next_op.is_some() {
5555
let op = next_op.take().unwrap();
56-
let interval = self.next_iv_before(force_end).unwrap_or_else(|| Interval::new(0, 0));
56+
let interval = self
57+
.next_iv_with_len(expected_len)
58+
.unwrap_or_else(|| Interval::new(0, 0));
5759

5860
// cache the op if the interval is empty. e.g. last_op_before(Some(0))
5961
if interval.is_empty() {
@@ -79,7 +81,7 @@ where
7981
}
8082

8183
if find_op.is_some() {
82-
if let Some(end) = force_end {
84+
if let Some(end) = expected_len {
8385
// try to find the next op before the index if consume_len less than index
8486
if end > consume_len && self.has_next() {
8587
return self.next_with_len(Some(end - consume_len));
@@ -111,12 +113,12 @@ where
111113
}
112114
}
113115

114-
fn next_iv_before(&self, force_end: Option<usize>) -> Option<Interval> {
116+
fn next_iv_with_len(&self, expected_len: Option<usize>) -> Option<Interval> {
115117
let op = self.next_iter_op()?;
116118
let start = self.consume_count;
117-
let end = match force_end {
119+
let end = match expected_len {
118120
None => self.consume_count + op.len(),
119-
Some(index) => self.consume_count + min(index, op.len()),
121+
Some(expected_len) => self.consume_count + min(expected_len, op.len()),
120122
};
121123

122124
let intersect = Interval::new(start, end).intersect(self.consume_iv);
@@ -155,34 +157,34 @@ where
155157

156158
type SeekResult = Result<(), OTError>;
157159
pub trait Metric {
158-
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, index: usize) -> SeekResult;
160+
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, offset: usize) -> SeekResult;
159161
}
160162

161163
pub struct OpMetric();
162164

163165
impl Metric for OpMetric {
164-
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, index: usize) -> SeekResult {
165-
let _ = check_bound(cursor.op_index, index)?;
166+
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, offset: usize) -> SeekResult {
167+
let _ = check_bound(cursor.op_index, offset)?;
166168
let mut seek_cursor = OpCursor::new(cursor.delta, cursor.origin_iv);
167-
let mut offset = 0;
169+
let mut cur_offset = 0;
168170
while let Some((_, op)) = seek_cursor.iter.next() {
169-
offset += op.len();
170-
if offset > index {
171+
cur_offset += op.len();
172+
if cur_offset > offset {
171173
break;
172174
}
173175
}
174-
cursor.descend(offset);
176+
cursor.descend(cur_offset);
175177
Ok(())
176178
}
177179
}
178180

179-
pub struct CharMetric();
181+
pub struct Utf16CodeUnitMetric();
180182

181-
impl Metric for CharMetric {
182-
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, index: usize) -> SeekResult {
183-
if index > 0 {
184-
let _ = check_bound(cursor.consume_count, index)?;
185-
let _ = cursor.next_with_len(Some(index));
183+
impl Metric for Utf16CodeUnitMetric {
184+
fn seek<T: Attributes>(cursor: &mut OpCursor<T>, offset: usize) -> SeekResult {
185+
if offset > 0 {
186+
let _ = check_bound(cursor.consume_count, offset)?;
187+
let _ = cursor.next_with_len(Some(offset));
186188
}
187189

188190
Ok(())

‎shared-lib/lib-ot/src/core/delta/delta.rs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -187,7 +187,7 @@ where
187187
}
188188
},
189189
Operation::Insert(insert) => {
190-
inverted.delete(insert.count_of_utf16_code_units());
190+
inverted.delete(insert.utf16_size());
191191
},
192192
Operation::Delete(delete) => {
193193
inverted.insert(&chars.take(*delete as usize).collect::<String>(), op.get_attributes());
@@ -294,12 +294,12 @@ where
294294
(Some(Operation::Insert(insert)), _) => {
295295
// let composed_attrs = transform_attributes(&next_op1, &next_op2, true);
296296
a_prime.insert(&insert.s, insert.attributes.clone());
297-
b_prime.retain(insert.count_of_utf16_code_units(), insert.attributes.clone());
297+
b_prime.retain(insert.utf16_size(), insert.attributes.clone());
298298
next_op1 = ops1.next();
299299
},
300300
(_, Some(Operation::Insert(o_insert))) => {
301301
let composed_attrs = transform_op_attribute(&next_op1, &next_op2)?;
302-
a_prime.retain(o_insert.count_of_utf16_code_units(), composed_attrs.clone());
302+
a_prime.retain(o_insert.utf16_size(), composed_attrs.clone());
303303
b_prime.insert(&o_insert.s, composed_attrs);
304304
next_op2 = ops2.next();
305305
},

0 commit comments

Comments
 (0)