floem_editor_core/buffer/
diff.rs

1use std::{
2    borrow::Cow,
3    ops::Range,
4    sync::{
5        atomic::{self, AtomicU64},
6        Arc,
7    },
8};
9
10use lapce_xi_rope::Rope;
11
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub enum DiffResult<T> {
14    Left(T),
15    Both(T, T),
16    Right(T),
17}
18
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub struct DiffBothInfo {
21    pub left: Range<usize>,
22    pub right: Range<usize>,
23    pub skip: Option<Range<usize>>,
24}
25
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub enum DiffLines {
28    Left(Range<usize>),
29    Both(DiffBothInfo),
30    Right(Range<usize>),
31}
32
33pub enum DiffExpand {
34    Up(usize),
35    Down(usize),
36    All,
37}
38
39pub fn expand_diff_lines(
40    diff_lines: &mut [DiffLines],
41    line: usize,
42    expand: DiffExpand,
43    is_right: bool,
44) {
45    for diff_line in diff_lines.iter_mut() {
46        if let DiffLines::Both(info) = diff_line {
47            if (is_right && info.right.start == line) || (!is_right && info.left.start == line) {
48                match expand {
49                    DiffExpand::All => {
50                        info.skip = None;
51                    }
52                    DiffExpand::Up(n) => {
53                        if let Some(skip) = &mut info.skip {
54                            if n >= skip.len() {
55                                info.skip = None;
56                            } else {
57                                skip.start += n;
58                            }
59                        }
60                    }
61                    DiffExpand::Down(n) => {
62                        if let Some(skip) = &mut info.skip {
63                            if n >= skip.len() {
64                                info.skip = None;
65                            } else {
66                                skip.end -= n;
67                            }
68                        }
69                    }
70                }
71                break;
72            }
73        }
74    }
75}
76
77pub fn rope_diff(
78    left_rope: Rope,
79    right_rope: Rope,
80    rev: u64,
81    atomic_rev: Arc<AtomicU64>,
82    context_lines: Option<usize>,
83) -> Option<Vec<DiffLines>> {
84    let left_lines = left_rope.lines(..).collect::<Vec<Cow<str>>>();
85    let right_lines = right_rope.lines(..).collect::<Vec<Cow<str>>>();
86
87    let left_count = left_lines.len();
88    let right_count = right_lines.len();
89    let min_count = std::cmp::min(left_count, right_count);
90
91    let leading_equals = left_lines
92        .iter()
93        .zip(right_lines.iter())
94        .take_while(|p| p.0 == p.1)
95        .count();
96    let trailing_equals = left_lines
97        .iter()
98        .rev()
99        .zip(right_lines.iter().rev())
100        .take(min_count - leading_equals)
101        .take_while(|p| p.0 == p.1)
102        .count();
103
104    let left_diff_size = left_count - leading_equals - trailing_equals;
105    let right_diff_size = right_count - leading_equals - trailing_equals;
106
107    let table: Vec<Vec<u32>> = {
108        let mut table = vec![vec![0; right_diff_size + 1]; left_diff_size + 1];
109        let left_skip = left_lines.iter().skip(leading_equals).take(left_diff_size);
110        let right_skip = right_lines
111            .iter()
112            .skip(leading_equals)
113            .take(right_diff_size);
114
115        for (i, l) in left_skip.enumerate() {
116            for (j, r) in right_skip.clone().enumerate() {
117                if atomic_rev.load(atomic::Ordering::Acquire) != rev {
118                    return None;
119                }
120                table[i + 1][j + 1] = if l == r {
121                    table[i][j] + 1
122                } else {
123                    std::cmp::max(table[i][j + 1], table[i + 1][j])
124                };
125            }
126        }
127
128        table
129    };
130
131    let diff = {
132        let mut diff = Vec::with_capacity(left_diff_size + right_diff_size);
133        let mut i = left_diff_size;
134        let mut j = right_diff_size;
135        let mut li = left_lines.iter().rev().skip(trailing_equals);
136        let mut ri = right_lines.iter().skip(trailing_equals);
137
138        loop {
139            if atomic_rev.load(atomic::Ordering::Acquire) != rev {
140                return None;
141            }
142            if j > 0 && (i == 0 || table[i][j] == table[i][j - 1]) {
143                j -= 1;
144                diff.push(DiffResult::Right(ri.next().unwrap()));
145            } else if i > 0 && (j == 0 || table[i][j] == table[i - 1][j]) {
146                i -= 1;
147                diff.push(DiffResult::Left(li.next().unwrap()));
148            } else if i > 0 && j > 0 {
149                i -= 1;
150                j -= 1;
151                diff.push(DiffResult::Both(li.next().unwrap(), ri.next().unwrap()));
152            } else {
153                break;
154            }
155        }
156
157        diff
158    };
159
160    let mut changes = Vec::new();
161    let mut left_line = 0;
162    let mut right_line = 0;
163    if leading_equals > 0 {
164        changes.push(DiffLines::Both(DiffBothInfo {
165            left: 0..leading_equals,
166            right: 0..leading_equals,
167            skip: None,
168        }))
169    }
170    left_line += leading_equals;
171    right_line += leading_equals;
172
173    for diff in diff.iter().rev() {
174        if atomic_rev.load(atomic::Ordering::Acquire) != rev {
175            return None;
176        }
177        match diff {
178            DiffResult::Left(_) => {
179                match changes.last_mut() {
180                    Some(DiffLines::Left(r)) => r.end = left_line + 1,
181                    _ => changes.push(DiffLines::Left(left_line..left_line + 1)),
182                }
183                left_line += 1;
184            }
185            DiffResult::Both(_, _) => {
186                match changes.last_mut() {
187                    Some(DiffLines::Both(info)) => {
188                        info.left.end = left_line + 1;
189                        info.right.end = right_line + 1;
190                    }
191                    _ => changes.push(DiffLines::Both(DiffBothInfo {
192                        left: left_line..left_line + 1,
193                        right: right_line..right_line + 1,
194                        skip: None,
195                    })),
196                }
197                left_line += 1;
198                right_line += 1;
199            }
200            DiffResult::Right(_) => {
201                match changes.last_mut() {
202                    Some(DiffLines::Right(r)) => r.end = right_line + 1,
203                    _ => changes.push(DiffLines::Right(right_line..right_line + 1)),
204                }
205                right_line += 1;
206            }
207        }
208    }
209
210    if trailing_equals > 0 {
211        changes.push(DiffLines::Both(DiffBothInfo {
212            left: left_count - trailing_equals..left_count,
213            right: right_count - trailing_equals..right_count,
214            skip: None,
215        }));
216    }
217    if let Some(context_lines) = context_lines {
218        if !changes.is_empty() {
219            let changes_last = changes.len() - 1;
220            for (i, change) in changes.iter_mut().enumerate() {
221                if atomic_rev.load(atomic::Ordering::Acquire) != rev {
222                    return None;
223                }
224                if let DiffLines::Both(info) = change {
225                    if i == 0 || i == changes_last {
226                        if info.right.len() > context_lines {
227                            if i == 0 {
228                                info.skip = Some(0..info.right.len() - context_lines);
229                            } else {
230                                info.skip = Some(context_lines..info.right.len());
231                            }
232                        }
233                    } else if info.right.len() > context_lines * 2 {
234                        info.skip = Some(context_lines..info.right.len() - context_lines);
235                    }
236                }
237            }
238        }
239    }
240
241    Some(changes)
242}
floem_editor_core/buffer/diff.rs

floem_editor_core/buffer/
diff.rs
