1use super::{Seg, SegPath};
4use rustc_hash::FxHashMap;
5#[cfg(feature = "runtime-diagnostics")]
6use std::cell::Cell;
7use std::fmt;
8use std::mem::size_of;
9use std::rc::{Rc, Weak};
10
11const INLINE_ITER_DEPTH: usize = 16;
12const POOL_ENTRY_LIMIT: usize = 4096;
13
14#[derive(Clone, Copy, Debug, Default)]
18#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
19pub struct PrefixPathDiagnostics {
20 pub retain_calls: u64,
22 pub input_segments: u64,
24 pub cursor_attempts: u64,
27 pub cursor_hits: u64,
29 pub reused_prefix_segments: u64,
31 pub cursor_deep_fallbacks: u64,
33 pub handles_created: u64,
35 pub handles_live: u64,
37 pub nodes_created: u64,
39 pub nodes_live: u64,
41 pub nodes_peak: u64,
43 pub pool_hits: u64,
45 pub pool_misses: u64,
47 pub pool_clears: u64,
49 pub flat_exports: u64,
51 pub flat_export_segments: u64,
53 pub iterator_spills: u64,
55}
56
57#[cfg(feature = "runtime-diagnostics")]
58thread_local! {
59 static COUNTERS: Cell<PrefixPathDiagnostics> = Cell::new(PrefixPathDiagnostics::default());
60}
61
62macro_rules! count {
65 ($action:expr) => {
66 #[cfg(feature = "runtime-diagnostics")]
67 {
68 record_count($action);
69 }
70 };
71}
72
73#[cfg(feature = "runtime-diagnostics")]
74fn record_count(f: impl FnOnce(&mut PrefixPathDiagnostics)) {
75 let _ = COUNTERS.try_with(|cell| {
78 let mut counters = cell.get();
79 f(&mut counters);
80 cell.set(counters);
81 });
82}
83
84pub fn prefix_path_diagnostics() -> PrefixPathDiagnostics {
87 #[cfg(feature = "runtime-diagnostics")]
88 {
89 COUNTERS.with(Cell::get)
90 }
91 #[cfg(not(feature = "runtime-diagnostics"))]
92 {
93 PrefixPathDiagnostics::default()
94 }
95}
96
97#[derive(Clone, Copy, Debug)]
100#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
101pub struct PrefixPathLayouts {
102 pub path_body: usize,
104 pub node_body: usize,
106 pub pool_entry: usize,
108 pub pool_body: usize,
110 pub iterator_body: usize,
112 pub assumed_rc_header: usize,
114}
115
116pub fn prefix_path_layouts() -> PrefixPathLayouts {
118 PrefixPathLayouts {
119 path_body: size_of::<PrefixPath>(),
120 node_body: size_of::<PathNode>(),
121 pool_entry: size_of::<((usize, Seg), Weak<PathNode>)>(),
122 pool_body: size_of::<PrefixPathPool>(),
123 iterator_body: size_of::<PrefixPathIter<'_>>(),
124 assumed_rc_header: 2 * size_of::<usize>(),
125 }
126}
127
128struct PathNode {
129 parent: Option<Rc<PathNode>>,
130 segment: Seg,
131}
132
133impl PathNode {
134 fn new(parent: Option<Rc<PathNode>>, segment: Seg) -> Rc<Self> {
135 count!(|c| {
136 c.nodes_created += 1;
137 c.nodes_live += 1;
138 c.nodes_peak = c.nodes_peak.max(c.nodes_live);
139 });
140 Rc::new(Self { parent, segment })
141 }
142}
143
144impl Drop for PathNode {
145 fn drop(&mut self) {
146 count!(|c| c.nodes_live -= 1);
147 let mut parent = self.parent.take();
150 while let Some(node) = parent {
151 match Rc::try_unwrap(node) {
152 Ok(mut unique) => parent = unique.parent.take(),
153 Err(_) => break,
154 }
155 }
156 }
157}
158
159pub struct PrefixPath {
163 tail: Option<Rc<PathNode>>,
164 len: usize,
165}
166
167impl PrefixPath {
168 fn from_tail(tail: Option<Rc<PathNode>>, len: usize) -> Self {
169 count!(|c| {
170 c.handles_created += 1;
171 c.handles_live += 1;
172 });
173 Self { tail, len }
174 }
175
176 pub fn from_segments(segments: &[Seg]) -> Self {
179 let mut path = Self::default();
180 for segment in segments {
181 path.push(segment.clone());
182 }
183 path
184 }
185
186 pub fn len(&self) -> usize {
188 self.len
189 }
190
191 pub fn is_empty(&self) -> bool {
193 self.len == 0
194 }
195
196 pub fn first(&self) -> Option<&Seg> {
198 self.get(0)
199 }
200
201 pub fn last(&self) -> Option<&Seg> {
203 self.tail.as_deref().map(|node| &node.segment)
204 }
205
206 pub fn get(&self, index: usize) -> Option<&Seg> {
209 if index >= self.len {
210 return None;
211 }
212 let mut node = self.tail.as_deref()?;
213 for _ in 0..self.len - index - 1 {
214 node = node.parent.as_deref()?;
215 }
216 Some(&node.segment)
217 }
218
219 pub fn iter(&self) -> PrefixPathIter<'_> {
221 PrefixPathIter::new(self)
222 }
223
224 pub fn format(&self, rel_root: Option<&str>) -> String {
227 super::path_str_iter(self.iter(), rel_root)
228 }
229
230 pub fn to_vec(&self) -> SegPath {
232 count!(|c| {
233 c.flat_exports += 1;
234 c.flat_export_segments += self.len as u64;
235 });
236 let mut result = Vec::with_capacity(self.len);
239 let mut node = self.tail.as_deref();
240 while let Some(current) = node {
241 result.push(current.segment.clone());
242 node = current.parent.as_deref();
243 }
244 result.reverse();
245 result
246 }
247
248 pub fn push(&mut self, segment: Seg) {
250 self.tail = Some(PathNode::new(self.tail.take(), segment));
251 self.len += 1;
252 }
253
254 pub fn pop(&mut self) -> Option<Seg> {
256 let tail = self.tail.take()?;
257 let result = tail.segment.clone();
258 self.tail = tail.parent.clone();
259 self.len -= 1;
260 Some(result)
261 }
262
263 pub fn clear(&mut self) {
265 self.tail = None;
266 self.len = 0;
267 }
268
269 pub fn prefix_node_ids(&self) -> impl Iterator<Item = usize> + '_ {
272 self.prefix_nodes().map(|(id, _)| id)
273 }
274
275 pub fn prefix_nodes(&self) -> impl Iterator<Item = (usize, &Seg)> + '_ {
278 std::iter::successors(self.tail.as_deref(), |node| node.parent.as_deref())
279 .map(|node| (node as *const PathNode as usize, &node.segment))
280 }
281}
282
283impl Default for PrefixPath {
284 fn default() -> Self {
285 Self::from_tail(None, 0)
286 }
287}
288
289impl Clone for PrefixPath {
290 fn clone(&self) -> Self {
291 Self::from_tail(self.tail.clone(), self.len)
292 }
293}
294
295#[cfg(feature = "runtime-diagnostics")]
296impl Drop for PrefixPath {
297 fn drop(&mut self) {
298 count!(|c| c.handles_live -= 1);
299 }
300}
301
302impl From<SegPath> for PrefixPath {
303 fn from(segments: SegPath) -> Self {
304 let mut path = Self::default();
305 for segment in segments {
306 path.push(segment);
307 }
308 path
309 }
310}
311
312impl fmt::Debug for PrefixPath {
313 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
314 f.debug_list().entries(self.iter()).finish()
315 }
316}
317
318impl PartialEq for PrefixPath {
319 fn eq(&self, other: &Self) -> bool {
320 self.len == other.len && self.iter().eq(other.iter())
321 }
322}
323
324impl Eq for PrefixPath {}
325
326pub struct PrefixPathIter<'a> {
329 inline: [Option<&'a PathNode>; INLINE_ITER_DEPTH],
330 spill: Option<Vec<&'a PathNode>>,
331 front: usize,
332 back: usize,
333}
334
335impl<'a> PrefixPathIter<'a> {
336 fn new(path: &'a PrefixPath) -> Self {
337 let mut result = Self {
338 inline: [None; INLINE_ITER_DEPTH],
339 spill: None,
340 front: 0,
341 back: path.len,
342 };
343 if path.len > INLINE_ITER_DEPTH {
344 count!(|c| c.iterator_spills += 1);
345 result.spill = Some(Vec::with_capacity(path.len));
346 }
347 let mut node = path.tail.as_deref();
348 let mut index = 0;
349 while let Some(current) = node {
350 if let Some(spill) = &mut result.spill {
351 spill.push(current);
352 } else {
353 result.inline[index] = Some(current);
354 }
355 index += 1;
356 node = current.parent.as_deref();
357 }
358 result
359 }
360
361 fn reverse_at(&self, index: usize) -> &'a Seg {
362 match &self.spill {
363 Some(spill) => &spill[index].segment,
364 None => {
365 &self.inline[index]
366 .expect("complete prefix ancestry")
367 .segment
368 }
369 }
370 }
371}
372
373impl<'a> Iterator for PrefixPathIter<'a> {
374 type Item = &'a Seg;
375
376 fn next(&mut self) -> Option<Self::Item> {
377 if self.front == self.back {
378 return None;
379 }
380 self.back -= 1;
381 Some(self.reverse_at(self.back))
382 }
383
384 fn size_hint(&self) -> (usize, Option<usize>) {
385 let remaining = self.back - self.front;
386 (remaining, Some(remaining))
387 }
388}
389
390impl DoubleEndedIterator for PrefixPathIter<'_> {
391 fn next_back(&mut self) -> Option<Self::Item> {
392 if self.front == self.back {
393 return None;
394 }
395 let index = self.front;
396 self.front += 1;
397 Some(self.reverse_at(index))
398 }
399}
400
401impl ExactSizeIterator for PrefixPathIter<'_> {}
402impl std::iter::FusedIterator for PrefixPathIter<'_> {}
403
404impl<'a> IntoIterator for &'a PrefixPath {
405 type Item = &'a Seg;
406 type IntoIter = PrefixPathIter<'a>;
407
408 fn into_iter(self) -> Self::IntoIter {
409 self.iter()
410 }
411}
412
413#[derive(Default)]
416pub struct PrefixPathPool {
417 entries: FxHashMap<(usize, Seg), Weak<PathNode>>,
418 cursor_tail: Weak<PathNode>,
420 cursor_len: usize,
421}
422
423#[derive(Clone, Copy, Debug)]
425pub struct PrefixPathPoolStats {
426 pub cursor_weak_entries: usize,
429 pub cursor_dead_entries: usize,
432 pub cursor_depth: usize,
434 pub entries: usize,
436 pub usable_capacity: usize,
438 pub entry_limit: usize,
440 pub dead_entries: usize,
442}
443
444impl PrefixPathPool {
445 pub fn retain(&mut self, segments: &[Seg]) -> Rc<PrefixPath> {
447 Rc::new(self.retain_value(segments))
448 }
449
450 pub fn retain_value(&mut self, segments: &[Seg]) -> PrefixPath {
453 count!(|c| {
454 c.retain_calls += 1;
455 c.input_segments += segments.len() as u64;
456 });
457 let mut parent: Option<Rc<PathNode>> = None;
458 let mut reused = 0;
459 if segments.len() > INLINE_ITER_DEPTH {
460 count!(|c| c.cursor_deep_fallbacks += 1);
461 } else if !segments.is_empty() && self.cursor_len != 0 {
462 count!(|c| c.cursor_attempts += 1);
463 if let Some(tail) = self.cursor_tail.upgrade() {
464 let mut ancestors: [Option<&Rc<PathNode>>; INLINE_ITER_DEPTH] =
467 [None; INLINE_ITER_DEPTH];
468 let mut node = Some(&tail);
469 let mut index = self.cursor_len;
470 while let Some(current) = node {
471 index -= 1;
472 ancestors[index] = Some(current);
473 node = current.parent.as_ref();
474 }
475 for (segment, ancestor) in segments.iter().zip(&ancestors[..self.cursor_len]) {
476 if segment != &ancestor.expect("complete cursor ancestry").segment {
477 break;
478 }
479 reused += 1;
480 }
481 if reused != 0 {
482 parent = Some(Rc::clone(
483 ancestors[reused - 1].expect("matched cursor prefix"),
484 ));
485 count!(|c| {
486 c.cursor_hits += 1;
487 c.reused_prefix_segments += reused as u64;
488 });
489 }
490 }
491 }
492 for segment in &segments[reused..] {
493 let parent_id = parent.as_ref().map_or(0, |node| Rc::as_ptr(node) as usize);
494 let key = (parent_id, segment.clone());
495 let node = match self.entries.get(&key).and_then(Weak::upgrade) {
496 Some(node) => {
497 count!(|c| c.pool_hits += 1);
500 node
501 }
502 None => {
503 count!(|c| c.pool_misses += 1);
504 if self.entries.len() >= POOL_ENTRY_LIMIT {
505 self.entries.clear();
506 count!(|c| c.pool_clears += 1);
507 }
508 let node = PathNode::new(parent.clone(), segment.clone());
509 self.entries.insert(key, Rc::downgrade(&node));
510 node
511 }
512 };
513 parent = Some(node);
514 }
515 if !segments.is_empty() && segments.len() <= INLINE_ITER_DEPTH {
516 self.cursor_tail = Rc::downgrade(parent.as_ref().expect("nonempty retained path"));
517 self.cursor_len = segments.len();
518 } else {
519 self.cursor_tail = Weak::new();
520 self.cursor_len = 0;
521 }
522 PrefixPath::from_tail(parent, segments.len())
525 }
526
527 pub fn stats(&self) -> PrefixPathPoolStats {
529 PrefixPathPoolStats {
530 cursor_weak_entries: usize::from(self.cursor_len != 0),
531 cursor_dead_entries: usize::from(
532 self.cursor_len != 0 && self.cursor_tail.strong_count() == 0,
533 ),
534 cursor_depth: self.cursor_len,
535 entries: self.entries.len(),
536 usable_capacity: self.entries.capacity(),
537 entry_limit: POOL_ENTRY_LIMIT,
538 dead_entries: self
539 .entries
540 .values()
541 .filter(|node| node.strong_count() == 0)
542 .count(),
543 }
544 }
545}
546
547#[cfg(test)]
548#[path = "../../tests/private/prefix_path_test.rs"]
549mod tests;