xi_core_lib/
line_cache_shadow.rs

1// Copyright 2017 The xi-editor Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Data structures for tracking the state of the front-end's line cache
16//! and preparing render plans to update it.
17
18use std::cmp::{max, min};
19use std::fmt;
20
21const SCROLL_SLOP: usize = 2;
22const PRESERVE_EXTENT: usize = 1000;
23
24/// The line cache shadow tracks the state of the line cache in the front-end.
25/// Any content marked as valid here is up-to-date in the current state of the
26/// view. Also, if `dirty` is false, then the entire line cache is valid.
27#[derive(Debug)]
28pub struct LineCacheShadow {
29    spans: Vec<Span>,
30    dirty: bool,
31}
32
33type Validity = u8;
34
35pub const INVALID: Validity = 0;
36pub const TEXT_VALID: Validity = 1;
37pub const STYLES_VALID: Validity = 2;
38pub const CURSOR_VALID: Validity = 4;
39pub const ALL_VALID: Validity = 7;
40
41pub struct Span {
42    /// Number of lines in this span. Units are visual lines in the
43    /// current state of the view.
44    pub n: usize,
45    /// Starting line number. Units are visual lines in the front end's
46    /// current cache state (i.e. the last one rendered). Note: this is
47    /// irrelevant if validity is 0.
48    pub start_line_num: usize,
49    /// Validity of lines in this span, consisting of the above constants or'ed.
50    pub validity: Validity,
51}
52
53/// Builder for `LineCacheShadow` object.
54pub struct Builder {
55    spans: Vec<Span>,
56    dirty: bool,
57}
58
59#[derive(Clone, Copy, PartialEq)]
60pub enum RenderTactic {
61    /// Discard all content for this span. Used to keep storage reasonable.
62    Discard,
63    /// Preserve existing content.
64    Preserve,
65    /// Render content if it is invalid.
66    Render,
67}
68
69pub struct RenderPlan {
70    /// Each span is a number of lines and a tactic.
71    pub spans: Vec<(usize, RenderTactic)>,
72}
73
74pub struct PlanIterator<'a> {
75    lc_shadow: &'a LineCacheShadow,
76    plan: &'a RenderPlan,
77    shadow_ix: usize,
78    shadow_line_num: usize,
79    plan_ix: usize,
80    plan_line_num: usize,
81}
82
83pub struct PlanSegment {
84    /// Line number of start of segment, visual lines in current view state.
85    pub our_line_num: usize,
86    /// Line number of start of segment, visual lines in client's cache, if validity != 0.
87    pub their_line_num: usize,
88    /// Number of visual lines in this segment.
89    pub n: usize,
90    /// Validity of this segment in client's cache.
91    pub validity: Validity,
92    /// Tactic for rendering this segment.
93    pub tactic: RenderTactic,
94}
95
96impl Builder {
97    pub fn new() -> Builder {
98        Builder { spans: Vec::new(), dirty: false }
99    }
100
101    pub fn build(self) -> LineCacheShadow {
102        LineCacheShadow { spans: self.spans, dirty: self.dirty }
103    }
104
105    pub fn add_span(&mut self, n: usize, start_line_num: usize, validity: Validity) {
106        if n > 0 {
107            if let Some(last) = self.spans.last_mut() {
108                if last.validity == validity
109                    && (validity == INVALID || last.start_line_num + last.n == start_line_num)
110                {
111                    last.n += n;
112                    return;
113                }
114            }
115            self.spans.push(Span { n, start_line_num, validity });
116        }
117    }
118
119    pub fn set_dirty(&mut self, dirty: bool) {
120        self.dirty = dirty;
121    }
122}
123
124impl LineCacheShadow {
125    pub fn edit(&mut self, start: usize, end: usize, replace: usize) {
126        let mut b = Builder::new();
127        let mut line_num = 0;
128        let mut i = 0;
129        while i < self.spans.len() {
130            let span = &self.spans[i];
131            if line_num + span.n <= start {
132                b.add_span(span.n, span.start_line_num, span.validity);
133                line_num += span.n;
134                i += 1;
135            } else {
136                b.add_span(start - line_num, span.start_line_num, span.validity);
137                break;
138            }
139        }
140        b.add_span(replace, 0, INVALID);
141        for span in &self.spans[i..] {
142            if line_num + span.n > end {
143                let offset = end.saturating_sub(line_num);
144                b.add_span(span.n - offset, span.start_line_num + offset, span.validity);
145            }
146            line_num += span.n;
147        }
148        b.set_dirty(true);
149        *self = b.build();
150    }
151
152    pub fn partial_invalidate(&mut self, start: usize, end: usize, invalid: Validity) {
153        let mut clean = true;
154        let mut line_num = 0;
155        for span in &self.spans {
156            if start < line_num + span.n && end > line_num && (span.validity & invalid) != 0 {
157                clean = false;
158                break;
159            }
160            line_num += span.n;
161        }
162        if clean {
163            return;
164        }
165
166        let mut b = Builder::new();
167        let mut line_num = 0;
168        for span in &self.spans {
169            if start > line_num {
170                b.add_span(min(span.n, start - line_num), span.start_line_num, span.validity);
171            }
172            let invalid_start = max(start, line_num);
173            let invalid_end = min(end, line_num + span.n);
174            if invalid_end > invalid_start {
175                b.add_span(
176                    invalid_end - invalid_start,
177                    span.start_line_num + (invalid_start - line_num),
178                    span.validity & !invalid,
179                );
180            }
181            if line_num + span.n > end {
182                let offset = end.saturating_sub(line_num);
183                b.add_span(span.n - offset, span.start_line_num + offset, span.validity);
184            }
185            line_num += span.n;
186        }
187        b.set_dirty(true);
188        *self = b.build();
189    }
190
191    pub fn needs_render(&self, plan: &RenderPlan) -> bool {
192        self.dirty
193            || self
194                .iter_with_plan(plan)
195                .any(|seg| seg.tactic == RenderTactic::Render && seg.validity != ALL_VALID)
196    }
197
198    pub fn spans(&self) -> &[Span] {
199        &self.spans
200    }
201
202    pub fn iter_with_plan<'a>(&'a self, plan: &'a RenderPlan) -> PlanIterator<'a> {
203        PlanIterator {
204            lc_shadow: self,
205            plan,
206            shadow_ix: 0,
207            shadow_line_num: 0,
208            plan_ix: 0,
209            plan_line_num: 0,
210        }
211    }
212}
213
214impl Default for LineCacheShadow {
215    fn default() -> LineCacheShadow {
216        Builder::new().build()
217    }
218}
219
220impl<'a> Iterator for PlanIterator<'a> {
221    type Item = PlanSegment;
222
223    fn next(&mut self) -> Option<PlanSegment> {
224        if self.shadow_ix == self.lc_shadow.spans.len() || self.plan_ix == self.plan.spans.len() {
225            return None;
226        }
227        let shadow_span = &self.lc_shadow.spans[self.shadow_ix];
228        let plan_span = &self.plan.spans[self.plan_ix];
229        let start = max(self.shadow_line_num, self.plan_line_num);
230        let end = min(self.shadow_line_num + shadow_span.n, self.plan_line_num + plan_span.0);
231        let result = PlanSegment {
232            our_line_num: start,
233            their_line_num: shadow_span.start_line_num + (start - self.shadow_line_num),
234            n: end - start,
235            validity: shadow_span.validity,
236            tactic: plan_span.1,
237        };
238
239        if end == self.shadow_line_num + shadow_span.n {
240            self.shadow_line_num = end;
241            self.shadow_ix += 1;
242        }
243        if end == self.plan_line_num + plan_span.0 {
244            self.plan_line_num = end;
245            self.plan_ix += 1;
246        }
247        Some(result)
248    }
249}
250
251impl RenderPlan {
252    /// This function implements the policy of what to discard, what to preserve, and
253    /// what to render.
254    pub fn create(total_height: usize, first_line: usize, height: usize) -> RenderPlan {
255        let mut spans = Vec::new();
256        let mut last = 0;
257        let first_line = min(first_line, total_height);
258        if first_line > PRESERVE_EXTENT {
259            last = first_line - PRESERVE_EXTENT;
260            spans.push((last, RenderTactic::Discard));
261        }
262        if first_line > SCROLL_SLOP {
263            let n = first_line - SCROLL_SLOP - last;
264            spans.push((n, RenderTactic::Preserve));
265            last += n;
266        }
267        let render_end = min(first_line + height + SCROLL_SLOP, total_height);
268        spans.push((render_end - last, RenderTactic::Render));
269        last = render_end;
270        let preserve_end = min(first_line + height + PRESERVE_EXTENT, total_height);
271        if preserve_end > last {
272            spans.push((preserve_end - last, RenderTactic::Preserve));
273            last = preserve_end;
274        }
275        if total_height > last {
276            spans.push((total_height - last, RenderTactic::Discard));
277        }
278        RenderPlan { spans }
279    }
280
281    /// Upgrade a range of lines to the "Render" tactic.
282    pub fn request_lines(&mut self, start: usize, end: usize) {
283        let mut spans: Vec<(usize, RenderTactic)> = Vec::new();
284        let mut i = 0;
285        let mut line_num = 0;
286        while i < self.spans.len() {
287            let span = &self.spans[i];
288            if line_num + span.0 <= start {
289                spans.push(*span);
290                line_num += span.0;
291                i += 1;
292            } else {
293                if line_num < start {
294                    spans.push((start - line_num, span.1));
295                }
296                break;
297            }
298        }
299        spans.push((end - start, RenderTactic::Render));
300        for span in &self.spans[i..] {
301            if line_num + span.0 > end {
302                let offset = end.saturating_sub(line_num);
303                spans.push((span.0 - offset, span.1));
304            }
305            line_num += span.0;
306        }
307        self.spans = spans;
308    }
309}
310
311impl fmt::Debug for Span {
312    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
313        let validity = match self.validity {
314            TEXT_VALID => "text",
315            ALL_VALID => "all",
316            _other => "mixed",
317        };
318        if self.validity == INVALID {
319            write!(f, "({} invalid)", self.n)?;
320        } else {
321            write!(f, "({}: {}, {})", self.start_line_num, self.n, validity)?;
322        }
323        Ok(())
324    }
325}
xi_core_lib/line_cache_shadow.rs

xi_core_lib/
line_cache_shadow.rs
