1use std::{
2 cell::RefCell,
3 collections::{HashMap, VecDeque},
4 rc::Rc,
5};
6
7use crate::{
8 storage::{ByteStore, Document, SourceId, SourceRef},
9 text::{Glyph, display_text, glyphs, glyphs_from},
10};
11
12const CACHE_BYTES: usize = 16 * 1024 * 1024;
13const CACHE_ENTRIES: usize = 1024;
14const CHECKPOINT_GLYPHS: usize = 256;
15
16#[derive(Clone, Copy, Default)]
17struct Boundary {
18 byte: usize,
19 column: usize,
20}
21
22#[cfg(all(test, feature = "owner-census"))]
23mod census_tests {
24 use super::*;
25 use crate::storage::StoreWriter;
26
27 #[test]
28 fn inspection_preserves_wrapped_geometry_and_releases_owners() {
29 let mut writer = StoreWriter::new().unwrap();
30 let bytes = "\tlet café = \"日本 👩💻\";".repeat(400);
31 writer.append(bytes.as_bytes()).unwrap();
32 let store = writer.finish();
33 let source = store.source_ref(0, bytes.len()).unwrap();
34 let cache = Cache::default();
35 let lines: Vec<_> = [None, Some(24), Some(80)]
36 .into_iter()
37 .map(|width| cache.get_source(&store, source, width).unwrap())
38 .collect();
39 let addresses: Vec<_> = lines
40 .iter()
41 .map(|line| {
42 (
43 line.text.as_ptr(),
44 line.starts.as_ptr(),
45 line.checkpoints.as_ptr(),
46 Rc::strong_count(line),
47 )
48 })
49 .collect();
50 let pages = store.cache_census().unwrap();
51 let census = cache.census().unwrap();
52 assert_eq!(census["entries"], 3);
53 assert_eq!(
54 census["payload_counter_bytes"],
55 lines.iter().map(|line| line.bytes()).sum::<usize>()
56 );
57 assert_eq!(
58 census["payload_counter_bytes"],
59 census["recomputed_payload_bytes"]
60 );
61 assert_eq!(cache.census().unwrap(), census);
62 assert_eq!(store.cache_census().unwrap(), pages);
63 for (line, expected) in lines.iter().zip(addresses) {
64 assert_eq!(
65 (
66 line.text.as_ptr(),
67 line.starts.as_ptr(),
68 line.checkpoints.as_ptr(),
69 Rc::strong_count(line)
70 ),
71 expected
72 );
73 }
74 let weak: Vec<_> = lines.iter().map(Rc::downgrade).collect();
75 drop(lines);
76 drop(cache);
77 assert!(weak.iter().all(|line| line.upgrade().is_none()));
78 }
79}
80
81pub struct Line {
82 text: Box<str>,
83 columns: usize,
84 checkpoints: Vec<Boundary>,
85 starts: Vec<Boundary>,
86}
87
88impl Line {
89 fn new(text: String, width: Option<usize>) -> Self {
90 let mut checkpoints = Vec::new();
91 let mut starts = vec![Boundary::default()];
92 let mut used = 0;
93 let mut columns = 0;
94 for (index, glyph) in glyphs(&text, 4).enumerate() {
95 columns = glyph.column + glyph.width;
96 let boundary = Boundary {
97 byte: glyph.byte,
98 column: glyph.column,
99 };
100 if index % CHECKPOINT_GLYPHS == 0 {
101 checkpoints.push(boundary);
102 }
103 if let Some(width) = width {
104 if used > 0 && used + glyph.width > width {
105 starts.push(boundary);
106 used = 0;
107 }
108 used += glyph.width;
109 }
110 }
111 Self {
112 text: text.into_boxed_str(),
113 columns,
114 checkpoints,
115 starts,
116 }
117 }
118
119 fn bytes(&self) -> usize {
120 size_of::<Self>()
121 + self.text.len()
122 + (self.checkpoints.capacity() + self.starts.capacity()) * size_of::<Boundary>()
123 }
124
125 pub fn height(&self) -> usize {
126 self.starts.len()
127 }
128
129 pub fn columns(&self) -> usize {
130 self.columns
131 }
132
133 pub fn start_column(&self, part: usize) -> Option<usize> {
134 self.starts.get(part).map(|start| start.column)
135 }
136
137 pub fn part_for_column(&self, column: usize) -> usize {
138 self.starts
139 .partition_point(|start| start.column <= column)
140 .saturating_sub(1)
141 }
142
143 pub fn glyphs_from_column(&self, column: usize) -> impl Iterator<Item = Glyph<'_>> {
144 let checkpoint = self
145 .checkpoints
146 .get(
147 self.checkpoints
148 .partition_point(|point| point.column <= column)
149 .saturating_sub(1),
150 )
151 .copied()
152 .unwrap_or_default();
153 glyphs_from(&self.text, 4, checkpoint.byte, checkpoint.column)
154 }
155
156 pub fn byte_at_column(&self, column: usize) -> usize {
157 self.glyphs_from_column(column)
158 .find(|glyph| glyph.column + glyph.width > column)
159 .map_or(self.text.len(), |glyph| glyph.byte)
160 }
161
162 pub fn column_at_byte(&self, byte: usize) -> (usize, usize) {
163 let checkpoint = self
164 .checkpoints
165 .get(
166 self.checkpoints
167 .partition_point(|point| point.byte <= byte)
168 .saturating_sub(1),
169 )
170 .copied()
171 .unwrap_or_default();
172 glyphs_from(&self.text, 4, checkpoint.byte, checkpoint.column)
173 .take_while(|glyph| glyph.byte <= byte)
174 .last()
175 .map_or((0, 1), |glyph| (glyph.column, glyph.width))
176 }
177}
178
179#[derive(Clone, Copy, PartialEq, Eq, Hash)]
180enum SourceKey {
181 Patch(SourceId),
182 Stored(SourceRef),
183}
184
185type Key = (SourceKey, Option<usize>);
186
187#[derive(Default)]
188struct Entries {
189 lines: HashMap<Key, Rc<Line>>,
190 order: VecDeque<Key>,
191 bytes: usize,
192}
193
194#[derive(Default)]
195pub struct Cache {
196 entries: RefCell<Entries>,
197}
198
199impl Cache {
200 #[cfg(feature = "owner-census")]
201 pub(crate) fn census(&self) -> anyhow::Result<serde_json::Value> {
202 let entries = self.entries.try_borrow()?;
203 Ok(serde_json::json!({
204 "entries": entries.lines.len(), "map_capacity": entries.lines.capacity(),
205 "payload_counter_bytes": entries.bytes,
206 "recomputed_payload_bytes": entries.lines.values().map(|line| line.bytes()).sum::<usize>(),
207 "payload_limit_bytes": CACHE_BYTES, "entry_limit": CACHE_ENTRIES,
208 "text_bytes": entries.lines.values().map(|line| line.text.len()).sum::<usize>(),
209 "occupied_map_element_bytes": entries.lines.len() * size_of::<(Key, Rc<Line>)>(),
210 "fifo_length": entries.order.len(), "fifo_capacity": entries.order.capacity(),
211 "fifo_element_size_bytes": size_of::<Key>(),
212 }))
213 }
214
215 pub fn get(&self, doc: &Document, id: usize, width: Option<usize>) -> anyhow::Result<Rc<Line>> {
216 let file = doc.file_for_source(id);
217 self.get_or_insert((SourceKey::Patch(file.source_id(id)?), width), || {
218 Ok(Line::new(display_text(&file.bytes(id)?), width))
219 })
220 }
221
222 pub(crate) fn get_source(
223 &self,
224 store: &ByteStore,
225 source: SourceRef,
226 width: Option<usize>,
227 ) -> anyhow::Result<Rc<Line>> {
228 self.get_or_insert((SourceKey::Stored(source), width), || {
229 Ok(Line::new(display_text(&store.read_source(source)?), width))
230 })
231 }
232
233 fn get_or_insert(
234 &self,
235 key: Key,
236 build: impl FnOnce() -> anyhow::Result<Line>,
237 ) -> anyhow::Result<Rc<Line>> {
238 if let Some(line) = self.entries.borrow().lines.get(&key) {
239 return Ok(line.clone());
240 }
241 let line = Rc::new(build()?);
242 let bytes = line.bytes();
243 if bytes <= CACHE_BYTES {
244 let mut entries = self.entries.borrow_mut();
245 while entries.bytes + bytes > CACHE_BYTES || entries.lines.len() >= CACHE_ENTRIES {
246 if let Some(old) = entries.order.pop_front()
247 && let Some(line) = entries.lines.remove(&old)
248 {
249 entries.bytes -= line.bytes();
250 }
251 }
252 entries.bytes += bytes;
253 entries.order.push_back(key);
254 entries.lines.insert(key, line.clone());
255 }
256 Ok(line)
257 }
258}