floem_editor_core/buffer/
mod.rs

1use std::{
2    borrow::{Borrow, Cow},
3    cmp::Ordering,
4    collections::BTreeSet,
5    fmt::Display,
6    sync::{
7        atomic::{self, AtomicU64},
8        Arc,
9    },
10};
11
12use lapce_xi_rope::{
13    multiset::Subset,
14    tree::{Node, NodeInfo},
15    Delta, DeltaBuilder, DeltaElement, Interval, Rope, RopeDelta,
16};
17
18use crate::{
19    cursor::CursorMode,
20    editor::EditType,
21    indent::{auto_detect_indent_style, IndentStyle},
22    line_ending::{LineEnding, LineEndingDetermination},
23    mode::Mode,
24    selection::Selection,
25    word::WordCursor,
26};
27
28pub mod diff;
29pub mod rope_text;
30
31use rope_text::*;
32
33#[derive(Clone)]
34enum Contents {
35    Edit {
36        /// Groups related edits together so that they are undone and re-done
37        /// together. For example, an auto-indent insertion would be un-done
38        /// along with the newline that triggered it.
39        undo_group: usize,
40        /// The subset of the characters of the union string from after this
41        /// revision that were added by this revision.
42        inserts: Subset,
43        /// The subset of the characters of the union string from after this
44        /// revision that were deleted by this revision.
45        deletes: Subset,
46    },
47    Undo {
48        /// The set of groups toggled between undone and done.
49        /// Just the `symmetric_difference` (XOR) of the two sets.
50        toggled_groups: BTreeSet<usize>, // set of undo_group id's
51        /// Used to store a reversible difference between the old
52        /// and new `deletes_from_union`
53        deletes_bitxor: Subset,
54    },
55}
56
57#[derive(Clone)]
58struct Revision {
59    num: u64,
60    max_undo_so_far: usize,
61    edit: Contents,
62    cursor_before: Option<CursorMode>,
63    cursor_after: Option<CursorMode>,
64}
65
66#[derive(Debug, Clone)]
67pub struct InvalLines {
68    pub start_line: usize,
69    pub inval_count: usize,
70    pub new_count: usize,
71    pub old_text: Rope,
72}
73
74#[derive(Clone)]
75pub struct Buffer {
76    rev_counter: u64,
77    pristine_rev_id: u64,
78    atomic_rev: Arc<AtomicU64>,
79
80    text: Rope,
81    revs: Vec<Revision>,
82    cur_undo: usize,
83    undos: BTreeSet<usize>,
84    undo_group_id: usize,
85    live_undos: Vec<usize>,
86    deletes_from_union: Subset,
87    undone_groups: BTreeSet<usize>,
88    tombstones: Rope,
89    this_edit_type: EditType,
90    last_edit_type: EditType,
91
92    indent_style: IndentStyle,
93    line_ending: LineEnding,
94}
95
96impl Display for Buffer {
97    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
98        f.write_str(&self.text().to_string())
99    }
100}
101
102impl Buffer {
103    pub fn new(text: impl Into<Rope>) -> Self {
104        let text = text.into();
105
106        // Determine the line ending of the text and adjust it if necessary
107        let line_ending = LineEndingDetermination::determine(&text);
108        let line_ending = line_ending.unwrap_or(LineEnding::Lf);
109
110        // Get rid of lone Cr's as Rope does not treat them as line endings
111        let text = line_ending.normalize_limited(&text);
112
113        let len = text.len();
114        Self {
115            text,
116
117            rev_counter: 1,
118            pristine_rev_id: 0,
119            atomic_rev: Arc::new(AtomicU64::new(0)),
120
121            revs: vec![Revision {
122                num: 0,
123                max_undo_so_far: 0,
124                edit: Contents::Undo {
125                    toggled_groups: BTreeSet::new(),
126                    deletes_bitxor: Subset::new(0),
127                },
128                cursor_before: None,
129                cursor_after: None,
130            }],
131            cur_undo: 1,
132            undos: BTreeSet::new(),
133            undo_group_id: 1,
134            live_undos: vec![0],
135            deletes_from_union: Subset::new(len),
136            undone_groups: BTreeSet::new(),
137            tombstones: Rope::default(),
138
139            this_edit_type: EditType::Other,
140            last_edit_type: EditType::Other,
141            indent_style: IndentStyle::DEFAULT_INDENT,
142            line_ending,
143        }
144    }
145
146    /// The current buffer revision
147    pub fn rev(&self) -> u64 {
148        self.revs.last().unwrap().num
149    }
150
151    /// Mark the buffer as pristine (aka 'saved')
152    pub fn set_pristine(&mut self) {
153        self.pristine_rev_id = self.rev();
154    }
155
156    pub fn is_pristine(&self) -> bool {
157        self.is_equivalent_revision(self.pristine_rev_id, self.rev())
158    }
159
160    pub fn set_cursor_before(&mut self, cursor: CursorMode) {
161        if let Some(rev) = self.revs.last_mut() {
162            rev.cursor_before = Some(cursor);
163        }
164    }
165
166    pub fn set_cursor_after(&mut self, cursor: CursorMode) {
167        if let Some(rev) = self.revs.last_mut() {
168            rev.cursor_after = Some(cursor);
169        }
170    }
171
172    fn is_equivalent_revision(&self, base_rev: u64, other_rev: u64) -> bool {
173        let base_subset = self
174            .find_rev(base_rev)
175            .map(|rev_index| self.deletes_from_cur_union_for_index(rev_index));
176        let other_subset = self
177            .find_rev(other_rev)
178            .map(|rev_index| self.deletes_from_cur_union_for_index(rev_index));
179
180        base_subset.is_some() && base_subset == other_subset
181    }
182
183    fn find_rev(&self, rev_id: u64) -> Option<usize> {
184        self.revs
185            .iter()
186            .enumerate()
187            .rev()
188            .find(|&(_, rev)| rev.num == rev_id)
189            .map(|(i, _)| i)
190    }
191
192    pub fn atomic_rev(&self) -> Arc<AtomicU64> {
193        self.atomic_rev.clone()
194    }
195
196    pub fn init_content(&mut self, content: Rope) {
197        if !content.is_empty() {
198            let line_ending = LineEndingDetermination::determine(&content);
199            self.line_ending = line_ending.unwrap_or(self.line_ending);
200
201            let content = self.line_ending.normalize_limited(&content);
202
203            let delta = Delta::simple_edit(Interval::new(0, 0), content, 0);
204            let (new_rev, new_text, new_tombstones, new_deletes_from_union) =
205                self.mk_new_rev(0, delta.clone());
206            self.apply_edit(
207                &delta,
208                new_rev,
209                new_text,
210                new_tombstones,
211                new_deletes_from_union,
212            );
213        }
214        self.set_pristine();
215    }
216
217    pub fn reload(&mut self, content: Rope, set_pristine: bool) -> (Rope, RopeDelta, InvalLines) {
218        // Determine the line ending of the new text
219        let line_ending = LineEndingDetermination::determine(&content);
220        self.line_ending = line_ending.unwrap_or(self.line_ending);
221
222        let content = self.line_ending.normalize_limited(&content);
223
224        let len = self.text.len();
225        let delta = Delta::simple_edit(Interval::new(0, len), content, len);
226        self.this_edit_type = EditType::Other;
227        let (text, delta, inval_lines) = self.add_delta(delta);
228        if set_pristine {
229            self.set_pristine();
230        }
231        (text, delta, inval_lines)
232    }
233
234    pub fn detect_indent(&mut self, default: impl FnOnce() -> IndentStyle) {
235        self.indent_style = auto_detect_indent_style(&self.text).unwrap_or_else(default);
236    }
237
238    pub fn indent_style(&self) -> IndentStyle {
239        self.indent_style
240    }
241
242    // TODO: users of this function should often be using Styling::indent_style instead!
243    pub fn indent_unit(&self) -> &'static str {
244        self.indent_style.as_str()
245    }
246
247    pub fn line_ending(&self) -> LineEnding {
248        self.line_ending
249    }
250
251    pub fn set_line_ending(&mut self, line_ending: LineEnding) {
252        self.line_ending = line_ending;
253    }
254
255    pub fn reset_edit_type(&mut self) {
256        self.last_edit_type = EditType::Other;
257    }
258
259    /// Apply edits, normalizes line endings before applying.
260    /// Returns `(Text before delta, delta, invalidated lines)`
261    pub fn edit<'a, I, E, S>(
262        &mut self,
263        edits: I,
264        edit_type: EditType,
265    ) -> (Rope, RopeDelta, InvalLines)
266    where
267        I: IntoIterator<Item = E>,
268        E: Borrow<(S, &'a str)>,
269        S: AsRef<Selection>,
270    {
271        let mut builder = DeltaBuilder::new(self.len());
272        let mut interval_rope = Vec::new();
273        for edit in edits {
274            let (selection, content) = edit.borrow();
275            let rope = Rope::from(content);
276            for region in selection.as_ref().regions() {
277                interval_rope.push((region.min(), region.max(), rope.clone()));
278            }
279        }
280        interval_rope.sort_by(|a, b| {
281            if a.0 == b.0 && a.1 == b.1 {
282                Ordering::Equal
283            } else if a.1 == b.0 {
284                Ordering::Less
285            } else {
286                a.1.cmp(&b.0)
287            }
288        });
289        for (start, end, rope) in interval_rope.into_iter() {
290            // TODO(minor): normalizing line endings here technically has an edge-case where it
291            // could be that we put a `\r` at the end of a replacement, then a `\n` at the start of
292            // a replacement right after it, and then it becomes a double newline.
293            // A possible alternative that might be better overall (?) would be to get the range of
294            // the delta and normalize that area after applying the delta.
295            builder.replace(start..end, self.line_ending.normalize(&rope));
296        }
297        let delta = builder.build();
298        self.this_edit_type = edit_type;
299        self.add_delta(delta)
300    }
301
302    pub fn normalize_line_endings(&mut self) -> Option<(Rope, RopeDelta, InvalLines)> {
303        let Some(delta) = self.line_ending.normalize_delta(&self.text) else {
304            // There were no changes needed
305            return None;
306        };
307        self.this_edit_type = EditType::NormalizeLineEndings;
308        Some(self.add_delta(delta))
309    }
310
311    // TODO: don't clone the delta and return it, if the caller needs it then they can clone it
312    /// Note: the delta's line-endings should be normalized.
313    fn add_delta(&mut self, delta: RopeDelta) -> (Rope, RopeDelta, InvalLines) {
314        let text = self.text.clone();
315
316        let undo_group = self.calculate_undo_group();
317        self.last_edit_type = self.this_edit_type;
318
319        let (new_rev, new_text, new_tombstones, new_deletes_from_union) =
320            self.mk_new_rev(undo_group, delta.clone());
321
322        let inval_lines = self.apply_edit(
323            &delta,
324            new_rev,
325            new_text,
326            new_tombstones,
327            new_deletes_from_union,
328        );
329
330        (text, delta, inval_lines)
331    }
332
333    fn apply_edit(
334        &mut self,
335        delta: &RopeDelta,
336        new_rev: Revision,
337        new_text: Rope,
338        new_tombstones: Rope,
339        new_deletes_from_union: Subset,
340    ) -> InvalLines {
341        self.rev_counter += 1;
342
343        let (iv, newlen) = delta.summary();
344        let old_logical_end_line = self.text.line_of_offset(iv.end) + 1;
345        let old_text = self.text.clone();
346
347        self.revs.push(new_rev);
348        self.text = new_text;
349        self.tombstones = new_tombstones;
350        self.deletes_from_union = new_deletes_from_union;
351
352        let logical_start_line = self.text.line_of_offset(iv.start);
353        let new_logical_end_line = self.text.line_of_offset(iv.start + newlen) + 1;
354        let old_hard_count = old_logical_end_line - logical_start_line;
355        let new_hard_count = new_logical_end_line - logical_start_line;
356
357        InvalLines {
358            start_line: logical_start_line,
359            inval_count: old_hard_count,
360            new_count: new_hard_count,
361            old_text,
362        }
363    }
364
365    fn calculate_undo_group(&mut self) -> usize {
366        let has_undos = !self.live_undos.is_empty();
367        let is_unbroken_group = !self.this_edit_type.breaks_undo_group(self.last_edit_type);
368
369        if has_undos && is_unbroken_group {
370            *self.live_undos.last().unwrap()
371        } else {
372            let undo_group = self.undo_group_id;
373            self.live_undos.truncate(self.cur_undo);
374            self.live_undos.push(undo_group);
375            self.cur_undo += 1;
376            self.undo_group_id += 1;
377            undo_group
378        }
379    }
380
381    /// Returns `(Revision, new text, new tombstones, new deletes from union)`
382    fn mk_new_rev(&self, undo_group: usize, delta: RopeDelta) -> (Revision, Rope, Rope, Subset) {
383        let (ins_delta, deletes) = delta.factor();
384
385        let deletes_at_rev = &self.deletes_from_union;
386
387        let union_ins_delta = ins_delta.transform_expand(deletes_at_rev, true);
388        let mut new_deletes = deletes.transform_expand(deletes_at_rev);
389
390        let new_inserts = union_ins_delta.inserted_subset();
391        if !new_inserts.is_empty() {
392            new_deletes = new_deletes.transform_expand(&new_inserts);
393        }
394        let cur_deletes_from_union = &self.deletes_from_union;
395        let text_ins_delta = union_ins_delta.transform_shrink(cur_deletes_from_union);
396        let text_with_inserts = text_ins_delta.apply(&self.text);
397        let rebased_deletes_from_union = cur_deletes_from_union.transform_expand(&new_inserts);
398
399        let undone = self.undone_groups.contains(&undo_group);
400        let new_deletes_from_union = {
401            let to_delete = if undone { &new_inserts } else { &new_deletes };
402            rebased_deletes_from_union.union(to_delete)
403        };
404
405        let (new_text, new_tombstones) = shuffle(
406            &text_with_inserts,
407            &self.tombstones,
408            &rebased_deletes_from_union,
409            &new_deletes_from_union,
410        );
411
412        let head_rev = self.revs.last().unwrap();
413        self.atomic_rev
414            .store(self.rev_counter, atomic::Ordering::Release);
415        (
416            Revision {
417                num: self.rev_counter,
418                max_undo_so_far: std::cmp::max(undo_group, head_rev.max_undo_so_far),
419                edit: Contents::Edit {
420                    undo_group,
421                    inserts: new_inserts,
422                    deletes: new_deletes,
423                },
424                cursor_before: None,
425                cursor_after: None,
426            },
427            new_text,
428            new_tombstones,
429            new_deletes_from_union,
430        )
431    }
432
433    fn deletes_from_union_for_index(&self, rev_index: usize) -> Cow<'_, Subset> {
434        self.deletes_from_union_before_index(rev_index + 1, true)
435    }
436
437    fn deletes_from_cur_union_for_index(&self, rev_index: usize) -> Cow<'_, Subset> {
438        let mut deletes_from_union = self.deletes_from_union_for_index(rev_index);
439        for rev in &self.revs[rev_index + 1..] {
440            if let Contents::Edit { ref inserts, .. } = rev.edit {
441                if !inserts.is_empty() {
442                    deletes_from_union = Cow::Owned(deletes_from_union.transform_union(inserts));
443                }
444            }
445        }
446        deletes_from_union
447    }
448
449    fn deletes_from_union_before_index(
450        &self,
451        rev_index: usize,
452        invert_undos: bool,
453    ) -> Cow<'_, Subset> {
454        let mut deletes_from_union = Cow::Borrowed(&self.deletes_from_union);
455        let mut undone_groups = Cow::Borrowed(&self.undone_groups);
456
457        // invert the changes to deletes_from_union starting in the present and working backwards
458        for rev in self.revs[rev_index..].iter().rev() {
459            deletes_from_union = match rev.edit {
460                Contents::Edit {
461                    ref inserts,
462                    ref deletes,
463                    ref undo_group,
464                    ..
465                } => {
466                    if undone_groups.contains(undo_group) {
467                        // no need to un-delete undone inserts since we'll just shrink them out
468                        Cow::Owned(deletes_from_union.transform_shrink(inserts))
469                    } else {
470                        let un_deleted = deletes_from_union.subtract(deletes);
471                        Cow::Owned(un_deleted.transform_shrink(inserts))
472                    }
473                }
474                Contents::Undo {
475                    ref toggled_groups,
476                    ref deletes_bitxor,
477                } => {
478                    if invert_undos {
479                        let new_undone = undone_groups
480                            .symmetric_difference(toggled_groups)
481                            .cloned()
482                            .collect();
483                        undone_groups = Cow::Owned(new_undone);
484                        Cow::Owned(deletes_from_union.bitxor(deletes_bitxor))
485                    } else {
486                        deletes_from_union
487                    }
488                }
489            }
490        }
491        deletes_from_union
492    }
493
494    fn find_first_undo_candidate_index(&self, toggled_groups: &BTreeSet<usize>) -> usize {
495        // find the lowest toggled undo group number
496        if let Some(lowest_group) = toggled_groups.iter().cloned().next() {
497            for (i, rev) in self.revs.iter().enumerate().rev() {
498                if rev.max_undo_so_far < lowest_group {
499                    return i + 1; // +1 since we know the one we just found doesn't have it
500                }
501            }
502            0
503        } else {
504            // no toggled groups, return past end
505            self.revs.len()
506        }
507    }
508
509    fn compute_undo(&self, groups: &BTreeSet<usize>) -> (Revision, Subset) {
510        let toggled_groups = self
511            .undone_groups
512            .symmetric_difference(groups)
513            .cloned()
514            .collect();
515        let first_candidate = self.find_first_undo_candidate_index(&toggled_groups);
516        // the `false` below: don't invert undos since our first_candidate is based on the current undo set, not past
517        let mut deletes_from_union = self
518            .deletes_from_union_before_index(first_candidate, false)
519            .into_owned();
520
521        for rev in &self.revs[first_candidate..] {
522            if let Contents::Edit {
523                ref undo_group,
524                ref inserts,
525                ref deletes,
526                ..
527            } = rev.edit
528            {
529                if groups.contains(undo_group) {
530                    if !inserts.is_empty() {
531                        deletes_from_union = deletes_from_union.transform_union(inserts);
532                    }
533                } else {
534                    if !inserts.is_empty() {
535                        deletes_from_union = deletes_from_union.transform_expand(inserts);
536                    }
537                    if !deletes.is_empty() {
538                        deletes_from_union = deletes_from_union.union(deletes);
539                    }
540                }
541            }
542        }
543
544        let cursor_before = self
545            .revs
546            .get(first_candidate)
547            .and_then(|rev| rev.cursor_before.clone());
548
549        let cursor_after = self
550            .revs
551            .get(first_candidate)
552            .and_then(|rev| match &rev.edit {
553                Contents::Edit { undo_group, .. } => Some(undo_group),
554                Contents::Undo { .. } => None,
555            })
556            .and_then(|group| {
557                let mut cursor = None;
558                for rev in &self.revs[first_candidate..] {
559                    if let Contents::Edit { ref undo_group, .. } = rev.edit {
560                        if group == undo_group {
561                            cursor = rev.cursor_after.as_ref();
562                        } else {
563                            break;
564                        }
565                    }
566                }
567                cursor.cloned()
568            });
569
570        let deletes_bitxor = self.deletes_from_union.bitxor(&deletes_from_union);
571        let max_undo_so_far = self.revs.last().unwrap().max_undo_so_far;
572        self.atomic_rev
573            .store(self.rev_counter, atomic::Ordering::Release);
574        (
575            Revision {
576                num: self.rev_counter,
577                max_undo_so_far,
578                edit: Contents::Undo {
579                    toggled_groups,
580                    deletes_bitxor,
581                },
582                cursor_before,
583                cursor_after,
584            },
585            deletes_from_union,
586        )
587    }
588
589    fn undo(
590        &mut self,
591        groups: BTreeSet<usize>,
592    ) -> (
593        Rope,
594        RopeDelta,
595        InvalLines,
596        Option<CursorMode>,
597        Option<CursorMode>,
598    ) {
599        let text = self.text.clone();
600        let (new_rev, new_deletes_from_union) = self.compute_undo(&groups);
601        let delta = Delta::synthesize(
602            &self.tombstones,
603            &self.deletes_from_union,
604            &new_deletes_from_union,
605        );
606        let new_text = delta.apply(&self.text);
607        let new_tombstones = shuffle_tombstones(
608            &self.text,
609            &self.tombstones,
610            &self.deletes_from_union,
611            &new_deletes_from_union,
612        );
613        self.undone_groups = groups;
614
615        let cursor_before = new_rev.cursor_before.clone();
616        let cursor_after = new_rev.cursor_after.clone();
617
618        let inval_lines = self.apply_edit(
619            &delta,
620            new_rev,
621            new_text,
622            new_tombstones,
623            new_deletes_from_union,
624        );
625
626        (text, delta, inval_lines, cursor_before, cursor_after)
627    }
628
629    pub fn do_undo(&mut self) -> Option<(Rope, RopeDelta, InvalLines, Option<CursorMode>)> {
630        if self.cur_undo <= 1 {
631            return None;
632        }
633
634        self.cur_undo -= 1;
635        self.undos.insert(self.live_undos[self.cur_undo]);
636        self.last_edit_type = EditType::Undo;
637        let (text, delta, inval_lines, cursor_before, _cursor_after) =
638            self.undo(self.undos.clone());
639
640        Some((text, delta, inval_lines, cursor_before))
641    }
642
643    pub fn do_redo(&mut self) -> Option<(Rope, RopeDelta, InvalLines, Option<CursorMode>)> {
644        if self.cur_undo >= self.live_undos.len() {
645            return None;
646        }
647
648        self.undos.remove(&self.live_undos[self.cur_undo]);
649        self.cur_undo += 1;
650        self.last_edit_type = EditType::Redo;
651        let (text, delta, inval_lines, _cursor_before, cursor_after) =
652            self.undo(self.undos.clone());
653
654        Some((text, delta, inval_lines, cursor_after))
655    }
656
657    pub fn move_word_forward(&self, offset: usize) -> usize {
658        self.move_n_words_forward(offset, 1)
659    }
660
661    pub fn move_word_backward(&self, offset: usize, mode: Mode) -> usize {
662        self.move_n_words_backward(offset, 1, mode)
663    }
664
665    pub fn char_at_offset(&self, offset: usize) -> Option<char> {
666        if self.is_empty() {
667            return None;
668        }
669        let offset = offset.min(self.len());
670        WordCursor::new(&self.text, offset)
671            .inner
672            .peek_next_codepoint()
673    }
674}
675
676impl RopeText for Buffer {
677    fn text(&self) -> &Rope {
678        &self.text
679    }
680}
681
682fn shuffle_tombstones(
683    text: &Rope,
684    tombstones: &Rope,
685    old_deletes_from_union: &Subset,
686    new_deletes_from_union: &Subset,
687) -> Rope {
688    // Taking the complement of deletes_from_union leads to an interleaving valid for swapped text and tombstones,
689    // allowing us to use the same method to insert the text into the tombstones.
690    let inverse_tombstones_map = old_deletes_from_union.complement();
691    let move_delta = Delta::synthesize(
692        text,
693        &inverse_tombstones_map,
694        &new_deletes_from_union.complement(),
695    );
696    move_delta.apply(tombstones)
697}
698
699fn shuffle(
700    text: &Rope,
701    tombstones: &Rope,
702    old_deletes_from_union: &Subset,
703    new_deletes_from_union: &Subset,
704) -> (Rope, Rope) {
705    // Delta that deletes the right bits from the text
706    let del_delta = Delta::synthesize(tombstones, old_deletes_from_union, new_deletes_from_union);
707    let new_text = del_delta.apply(text);
708    (
709        new_text,
710        shuffle_tombstones(
711            text,
712            tombstones,
713            old_deletes_from_union,
714            new_deletes_from_union,
715        ),
716    )
717}
718
719pub struct DeltaValueRegion<'a, N: NodeInfo + 'a> {
720    pub old_offset: usize,
721    pub new_offset: usize,
722    pub len: usize,
723    pub node: &'a Node<N>,
724}
725
726/// Modified version of `xi_rope::delta::InsertsIter` which includes the node
727pub struct InsertsValueIter<'a, N: NodeInfo + 'a> {
728    pos: usize,
729    last_end: usize,
730    els_iter: std::slice::Iter<'a, DeltaElement<N>>,
731}
732impl<'a, N: NodeInfo + 'a> InsertsValueIter<'a, N> {
733    pub fn new(delta: &'a Delta<N>) -> InsertsValueIter<'a, N> {
734        InsertsValueIter {
735            pos: 0,
736            last_end: 0,
737            els_iter: delta.els.iter(),
738        }
739    }
740}
741impl<'a, N: NodeInfo> Iterator for InsertsValueIter<'a, N> {
742    type Item = DeltaValueRegion<'a, N>;
743
744    fn next(&mut self) -> Option<Self::Item> {
745        for elem in &mut self.els_iter {
746            match *elem {
747                DeltaElement::Copy(b, e) => {
748                    self.pos += e - b;
749                    self.last_end = e;
750                }
751                DeltaElement::Insert(ref n) => {
752                    let result = Some(DeltaValueRegion {
753                        old_offset: self.last_end,
754                        new_offset: self.pos,
755                        len: n.len(),
756                        node: n,
757                    });
758                    self.pos += n.len();
759                    self.last_end += n.len();
760                    return result;
761                }
762            }
763        }
764        None
765    }
766}
767
768#[cfg(test)]
769mod test;