imara_diff/
slider_heuristic.rs

1use std::cmp::Ordering;
2use std::hash::Hash;
3use std::ops::{Add, Range};
4
5use crate::intern::Token;
6
7pub trait SliderHeuristic {
8    fn best_slider_end(&mut self, tokens: &[Token], hunk: Range<u32>, earliest_end: u32) -> u32;
9}
10
11impl<F> SliderHeuristic for F
12where
13    F: FnMut(&[Token], Range<u32>, u32) -> u32,
14{
15    fn best_slider_end(&mut self, tokens: &[Token], hunk: Range<u32>, earliest_end: u32) -> u32 {
16        self(tokens, hunk, earliest_end)
17    }
18}
19
20pub struct NoSliderHeuristic;
21
22impl SliderHeuristic for NoSliderHeuristic {
23    fn best_slider_end(&mut self, _tokens: &[Token], hunk: Range<u32>, _earliest_end: u32) -> u32 {
24        hunk.end
25    }
26}
27
28pub struct IndentHeuristic<IndentOfToken> {
29    indent_of_token: IndentOfToken,
30}
31
32impl<IndentOfToken> IndentHeuristic<IndentOfToken> {
33    pub fn new(indent_of_token: IndentOfToken) -> Self {
34        Self { indent_of_token }
35    }
36}
37
38impl<IndentOfToken: Fn(Token) -> IndentLevel> SliderHeuristic for IndentHeuristic<IndentOfToken> {
39    fn best_slider_end(&mut self, tokens: &[Token], hunk: Range<u32>, earliest_end: u32) -> u32 {
40        const MAX_SLIDING: u32 = 100;
41        // this is a pure insertation that can be moved freely up and down
42        // to get more intutive results apply a heuristic
43        let mut top_slider_end = earliest_end;
44        // TODO: why is this needed
45        if top_slider_end < hunk.start - 1 {
46            top_slider_end = hunk.start - 1;
47        }
48        if hunk.end > top_slider_end + MAX_SLIDING {
49            top_slider_end = hunk.end - MAX_SLIDING;
50        }
51        let group_size = hunk.end - hunk.start;
52        let mut best_score = Score::for_range(
53            top_slider_end - group_size..top_slider_end,
54            tokens,
55            &self.indent_of_token,
56        );
57        let mut best_slider_end = top_slider_end;
58        for slider_end in (top_slider_end + 1)..=hunk.end {
59            let score = Score::for_range(
60                slider_end - group_size..slider_end,
61                tokens,
62                &self.indent_of_token,
63            );
64            if score.is_improvement_over(best_score) {
65                best_score = score;
66                best_slider_end = slider_end;
67            }
68        }
69        best_slider_end
70    }
71}
72
73#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, PartialOrd)]
74pub struct IndentLevel(u8);
75
76impl IndentLevel {
77    /// line is empty or only contains whitespaces (or EOF)
78    const BLANK: IndentLevel = IndentLevel(u8::MAX);
79    const MAX: IndentLevel = IndentLevel(200);
80
81    pub fn for_ascii_line(src: impl IntoIterator<Item = u8>, tab_width: u8) -> IndentLevel {
82        let mut indent_level = IndentLevel(0);
83        for c in src {
84            match c {
85                b' ' => indent_level.0 += 1,
86                b'\t' => indent_level.0 += tab_width - indent_level.0 % tab_width,
87                b'\r' | b'\n' | b'\x0C' => (),
88                _ => return indent_level,
89            }
90            if indent_level >= Self::MAX {
91                return indent_level;
92            }
93        }
94        IndentLevel::BLANK
95    }
96
97    pub fn for_line(src: impl IntoIterator<Item = char>, tab_width: u8) -> IndentLevel {
98        let mut indent_level = IndentLevel(0);
99        for c in src {
100            match c {
101                ' ' => indent_level.0 += 1,
102                '\t' => indent_level.0 += tab_width - indent_level.0 % tab_width,
103                '\r' | '\n' | '\x0C' => (),
104                _ => return indent_level,
105            }
106            if indent_level >= Self::MAX {
107                return indent_level;
108            }
109        }
110        IndentLevel::BLANK
111    }
112
113    fn map_or<T>(self, default: T, f: impl FnOnce(u8) -> T) -> T {
114        if self == Self::BLANK {
115            default
116        } else {
117            f(self.0)
118        }
119    }
120
121    fn or(self, default: Self) -> Self {
122        if self == Self::BLANK {
123            default
124        } else {
125            self
126        }
127    }
128}
129
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub struct Indents {
132    /// indent level of the line/token
133    indent: IndentLevel,
134    /// indent level at the previous (non-blank) line
135    prev_indent: IndentLevel,
136    /// indent level at the next (non-blank) line
137    next_indent: IndentLevel,
138    /// How many consecutive lines above the split are blank?
139    leading_blanks: u8,
140    /// How many lines after the line following the split are blank?
141    trailing_blanks: u8,
142}
143
144const MAX_BLANKS: usize = 20;
145
146impl Indents {
147    fn at_token(
148        tokens: &[Token],
149        token_idx: usize,
150        indent_of_token: impl Fn(Token) -> IndentLevel,
151    ) -> Indents {
152        let (leading_blank_lines, indent_previous_line) = tokens[..token_idx]
153            .iter()
154            .rev()
155            .enumerate()
156            .find_map(|(i, &token)| {
157                if i == MAX_BLANKS {
158                    Some((i, IndentLevel(0)))
159                } else {
160                    let level = indent_of_token(token);
161                    if level == IndentLevel::BLANK {
162                        None
163                    } else {
164                        Some((i, level))
165                    }
166                }
167            })
168            .unwrap_or((token_idx, IndentLevel::BLANK));
169        let at_eof = token_idx == tokens.len();
170        let (trailing_blank_lines, indent_next_line) = if at_eof {
171            (0, IndentLevel::BLANK)
172        } else {
173            tokens[token_idx + 1..]
174                .iter()
175                .enumerate()
176                .find_map(|(i, &token)| {
177                    if i == MAX_BLANKS {
178                        Some((i, IndentLevel(0)))
179                    } else {
180                        let level = indent_of_token(token);
181                        if level == IndentLevel::BLANK {
182                            None
183                        } else {
184                            Some((i, level))
185                        }
186                    }
187                })
188                .unwrap_or((token_idx, IndentLevel::BLANK))
189        };
190        let indent = tokens
191            .get(token_idx)
192            .map_or(IndentLevel::BLANK, |&token| indent_of_token(token));
193        Indents {
194            indent,
195            prev_indent: indent_previous_line,
196            next_indent: indent_next_line,
197            leading_blanks: leading_blank_lines as u8,
198            trailing_blanks: trailing_blank_lines as u8,
199        }
200    }
201
202    fn score(&self) -> Score {
203        let mut penalty = 0;
204        if self.prev_indent == IndentLevel::BLANK && self.leading_blanks == 0 {
205            penalty += START_OF_FILE_PENALTY;
206        }
207        if self.next_indent == IndentLevel::BLANK && self.trailing_blanks == 0 {
208            penalty += END_OF_FILE_PENALTY;
209        }
210
211        let trailing_blank_lines = if self.indent == IndentLevel::BLANK {
212            self.trailing_blanks as i32 + 1
213        } else {
214            0
215        };
216        let total_blank_lines = trailing_blank_lines + self.leading_blanks as i32;
217        penalty += TOTAL_BLANK_LINE_WEIGHT * total_blank_lines
218            + trailing_blank_lines * TRAILING_BLANK_LINES_WEIGHT;
219        let indent = self.indent.or(self.next_indent);
220        if indent != IndentLevel::BLANK && self.prev_indent != IndentLevel::BLANK {
221            match indent.0.cmp(&self.prev_indent.0) {
222                Ordering::Equal => {}
223                // self.next_indent != IndentLevel::BLANK follows for free here
224                // since indent != BLANK and therefore self.next_indent <= indent < BLANK
225                Ordering::Less if self.next_indent.0 <= indent.0 => {
226                    penalty += if total_blank_lines != 0 {
227                        RELATIVE_DEDENT_WITH_BLANK_PENALTY
228                    } else {
229                        RELATIVE_DEDENT_PENALTY
230                    }
231                }
232                Ordering::Less => {
233                    penalty += if total_blank_lines != 0 {
234                        RELATIVE_OUTDENT_WITH_BLANK_PENALTY
235                    } else {
236                        RELATIVE_OUTDENT_PENALTY
237                    }
238                }
239                Ordering::Greater => {
240                    penalty += if total_blank_lines != 0 {
241                        RELATIVE_INDENT_WITH_BLANK_PENALTY
242                    } else {
243                        RELATIVE_INDENT_PENALTY
244                    }
245                }
246            }
247        }
248        Score {
249            indent: indent.map_or(-1, i32::from),
250            penalty,
251        }
252    }
253}
254
255const START_OF_FILE_PENALTY: i32 = 1;
256const END_OF_FILE_PENALTY: i32 = 21;
257const TOTAL_BLANK_LINE_WEIGHT: i32 = -30;
258const TRAILING_BLANK_LINES_WEIGHT: i32 = 6;
259
260const RELATIVE_INDENT_PENALTY: i32 = -4;
261const RELATIVE_INDENT_WITH_BLANK_PENALTY: i32 = 10;
262
263const RELATIVE_OUTDENT_PENALTY: i32 = 24;
264const RELATIVE_OUTDENT_WITH_BLANK_PENALTY: i32 = 17;
265
266const RELATIVE_DEDENT_PENALTY: i32 = 23;
267const RELATIVE_DEDENT_WITH_BLANK_PENALTY: i32 = 17;
268
269const INDENT_WEIGHT: i32 = 60;
270
271#[derive(PartialEq, Eq, Clone, Copy)]
272struct Score {
273    indent: i32,
274    penalty: i32,
275}
276
277impl Score {
278    fn for_range(
279        range: Range<u32>,
280        tokens: &[Token],
281        indent_of_token: impl Fn(Token) -> IndentLevel,
282    ) -> Score {
283        Indents::at_token(tokens, range.start as usize, &indent_of_token).score()
284            + Indents::at_token(tokens, range.end as usize, &indent_of_token).score()
285    }
286}
287
288impl Add for Score {
289    type Output = Score;
290
291    fn add(self, rhs: Self) -> Self::Output {
292        Score {
293            indent: self.indent + rhs.indent,
294            penalty: self.penalty + rhs.penalty,
295        }
296    }
297}
298
299impl Score {
300    fn is_improvement_over(self, prev_score: Self) -> bool {
301        // smaller indentation level is preferred (with a weight)
302        let indent_score = match prev_score.indent.cmp(&self.indent) {
303            Ordering::Less => INDENT_WEIGHT,
304            Ordering::Greater => -INDENT_WEIGHT,
305            Ordering::Equal => 0,
306        };
307        (indent_score + self.penalty - prev_score.penalty) <= 0
308    }
309}
imara_diff/slider_heuristic.rs

imara_diff/
slider_heuristic.rs
