use super::{Seg, SegPath};
use rustc_hash::FxHashMap;
#[cfg(feature = "runtime-diagnostics")]
use std::cell::Cell;
use std::fmt;
use std::mem::size_of;
use std::rc::{Rc, Weak};
const INLINE_ITER_DEPTH: usize = 16;
const POOL_ENTRY_LIMIT: usize = 4096;
#[derive(Clone, Copy, Debug, Default)]
#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
pub struct PrefixPathDiagnostics {
pub retain_calls: u64,
pub input_segments: u64,
pub cursor_attempts: u64,
pub cursor_hits: u64,
pub reused_prefix_segments: u64,
pub cursor_deep_fallbacks: u64,
pub handles_created: u64,
pub handles_live: u64,
pub nodes_created: u64,
pub nodes_live: u64,
pub nodes_peak: u64,
pub pool_hits: u64,
pub pool_misses: u64,
pub pool_clears: u64,
pub flat_exports: u64,
pub flat_export_segments: u64,
pub iterator_spills: u64,
}
#[cfg(feature = "runtime-diagnostics")]
thread_local! {
static COUNTERS: Cell<PrefixPathDiagnostics> = Cell::new(PrefixPathDiagnostics::default());
}
macro_rules! count {
($action:expr) => {
#[cfg(feature = "runtime-diagnostics")]
{
record_count($action);
}
};
}
#[cfg(feature = "runtime-diagnostics")]
fn record_count(f: impl FnOnce(&mut PrefixPathDiagnostics)) {
let _ = COUNTERS.try_with(|cell| {
let mut counters = cell.get();
f(&mut counters);
cell.set(counters);
});
}
pub fn prefix_path_diagnostics() -> PrefixPathDiagnostics {
#[cfg(feature = "runtime-diagnostics")]
{
COUNTERS.with(Cell::get)
}
#[cfg(not(feature = "runtime-diagnostics"))]
{
PrefixPathDiagnostics::default()
}
}
#[derive(Clone, Copy, Debug)]
#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
pub struct PrefixPathLayouts {
pub path_body: usize,
pub node_body: usize,
pub pool_entry: usize,
pub pool_body: usize,
pub iterator_body: usize,
pub assumed_rc_header: usize,
}
pub fn prefix_path_layouts() -> PrefixPathLayouts {
PrefixPathLayouts {
path_body: size_of::<PrefixPath>(),
node_body: size_of::<PathNode>(),
pool_entry: size_of::<((usize, Seg), Weak<PathNode>)>(),
pool_body: size_of::<PrefixPathPool>(),
iterator_body: size_of::<PrefixPathIter<'_>>(),
assumed_rc_header: 2 * size_of::<usize>(),
}
}
struct PathNode {
parent: Option<Rc<PathNode>>,
segment: Seg,
}
impl PathNode {
fn new(parent: Option<Rc<PathNode>>, segment: Seg) -> Rc<Self> {
count!(|c| {
c.nodes_created += 1;
c.nodes_live += 1;
c.nodes_peak = c.nodes_peak.max(c.nodes_live);
});
Rc::new(Self { parent, segment })
}
}
impl Drop for PathNode {
fn drop(&mut self) {
count!(|c| c.nodes_live -= 1);
let mut parent = self.parent.take();
while let Some(node) = parent {
match Rc::try_unwrap(node) {
Ok(mut unique) => parent = unique.parent.take(),
Err(_) => break,
}
}
}
}
pub struct PrefixPath {
tail: Option<Rc<PathNode>>,
len: usize,
}
impl PrefixPath {
fn from_tail(tail: Option<Rc<PathNode>>, len: usize) -> Self {
count!(|c| {
c.handles_created += 1;
c.handles_live += 1;
});
Self { tail, len }
}
pub fn from_segments(segments: &[Seg]) -> Self {
let mut path = Self::default();
for segment in segments {
path.push(segment.clone());
}
path
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn first(&self) -> Option<&Seg> {
self.get(0)
}
pub fn last(&self) -> Option<&Seg> {
self.tail.as_deref().map(|node| &node.segment)
}
pub fn get(&self, index: usize) -> Option<&Seg> {
if index >= self.len {
return None;
}
let mut node = self.tail.as_deref()?;
for _ in 0..self.len - index - 1 {
node = node.parent.as_deref()?;
}
Some(&node.segment)
}
pub fn iter(&self) -> PrefixPathIter<'_> {
PrefixPathIter::new(self)
}
pub fn format(&self, rel_root: Option<&str>) -> String {
super::path_str_iter(self.iter(), rel_root)
}
pub fn to_vec(&self) -> SegPath {
count!(|c| {
c.flat_exports += 1;
c.flat_export_segments += self.len as u64;
});
let mut result = Vec::with_capacity(self.len);
let mut node = self.tail.as_deref();
while let Some(current) = node {
result.push(current.segment.clone());
node = current.parent.as_deref();
}
result.reverse();
result
}
pub fn push(&mut self, segment: Seg) {
self.tail = Some(PathNode::new(self.tail.take(), segment));
self.len += 1;
}
pub fn pop(&mut self) -> Option<Seg> {
let tail = self.tail.take()?;
let result = tail.segment.clone();
self.tail = tail.parent.clone();
self.len -= 1;
Some(result)
}
pub fn clear(&mut self) {
self.tail = None;
self.len = 0;
}
pub fn prefix_node_ids(&self) -> impl Iterator<Item = usize> + '_ {
self.prefix_nodes().map(|(id, _)| id)
}
pub fn prefix_nodes(&self) -> impl Iterator<Item = (usize, &Seg)> + '_ {
std::iter::successors(self.tail.as_deref(), |node| node.parent.as_deref())
.map(|node| (node as *const PathNode as usize, &node.segment))
}
}
impl Default for PrefixPath {
fn default() -> Self {
Self::from_tail(None, 0)
}
}
impl Clone for PrefixPath {
fn clone(&self) -> Self {
Self::from_tail(self.tail.clone(), self.len)
}
}
#[cfg(feature = "runtime-diagnostics")]
impl Drop for PrefixPath {
fn drop(&mut self) {
count!(|c| c.handles_live -= 1);
}
}
impl From<SegPath> for PrefixPath {
fn from(segments: SegPath) -> Self {
let mut path = Self::default();
for segment in segments {
path.push(segment);
}
path
}
}
impl fmt::Debug for PrefixPath {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
impl PartialEq for PrefixPath {
fn eq(&self, other: &Self) -> bool {
self.len == other.len && self.iter().eq(other.iter())
}
}
impl Eq for PrefixPath {}
pub struct PrefixPathIter<'a> {
inline: [Option<&'a PathNode>; INLINE_ITER_DEPTH],
spill: Option<Vec<&'a PathNode>>,
front: usize,
back: usize,
}
impl<'a> PrefixPathIter<'a> {
fn new(path: &'a PrefixPath) -> Self {
let mut result = Self {
inline: [None; INLINE_ITER_DEPTH],
spill: None,
front: 0,
back: path.len,
};
if path.len > INLINE_ITER_DEPTH {
count!(|c| c.iterator_spills += 1);
result.spill = Some(Vec::with_capacity(path.len));
}
let mut node = path.tail.as_deref();
let mut index = 0;
while let Some(current) = node {
if let Some(spill) = &mut result.spill {
spill.push(current);
} else {
result.inline[index] = Some(current);
}
index += 1;
node = current.parent.as_deref();
}
result
}
fn reverse_at(&self, index: usize) -> &'a Seg {
match &self.spill {
Some(spill) => &spill[index].segment,
None => {
&self.inline[index]
.expect("complete prefix ancestry")
.segment
}
}
}
}
impl<'a> Iterator for PrefixPathIter<'a> {
type Item = &'a Seg;
fn next(&mut self) -> Option<Self::Item> {
if self.front == self.back {
return None;
}
self.back -= 1;
Some(self.reverse_at(self.back))
}
fn size_hint(&self) -> (usize, Option<usize>) {
let remaining = self.back - self.front;
(remaining, Some(remaining))
}
}
impl DoubleEndedIterator for PrefixPathIter<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.front == self.back {
return None;
}
let index = self.front;
self.front += 1;
Some(self.reverse_at(index))
}
}
impl ExactSizeIterator for PrefixPathIter<'_> {}
impl std::iter::FusedIterator for PrefixPathIter<'_> {}
impl<'a> IntoIterator for &'a PrefixPath {
type Item = &'a Seg;
type IntoIter = PrefixPathIter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[derive(Default)]
pub struct PrefixPathPool {
entries: FxHashMap<(usize, Seg), Weak<PathNode>>,
cursor_tail: Weak<PathNode>,
cursor_len: usize,
}
#[derive(Clone, Copy, Debug)]
pub struct PrefixPathPoolStats {
pub cursor_weak_entries: usize,
pub cursor_dead_entries: usize,
pub cursor_depth: usize,
pub entries: usize,
pub usable_capacity: usize,
pub entry_limit: usize,
pub dead_entries: usize,
}
impl PrefixPathPool {
pub fn retain(&mut self, segments: &[Seg]) -> Rc<PrefixPath> {
Rc::new(self.retain_value(segments))
}
pub fn retain_value(&mut self, segments: &[Seg]) -> PrefixPath {
count!(|c| {
c.retain_calls += 1;
c.input_segments += segments.len() as u64;
});
let mut parent: Option<Rc<PathNode>> = None;
let mut reused = 0;
if segments.len() > INLINE_ITER_DEPTH {
count!(|c| c.cursor_deep_fallbacks += 1);
} else if !segments.is_empty() && self.cursor_len != 0 {
count!(|c| c.cursor_attempts += 1);
if let Some(tail) = self.cursor_tail.upgrade() {
let mut ancestors: [Option<&Rc<PathNode>>; INLINE_ITER_DEPTH] =
[None; INLINE_ITER_DEPTH];
let mut node = Some(&tail);
let mut index = self.cursor_len;
while let Some(current) = node {
index -= 1;
ancestors[index] = Some(current);
node = current.parent.as_ref();
}
for (segment, ancestor) in segments.iter().zip(&ancestors[..self.cursor_len]) {
if segment != &ancestor.expect("complete cursor ancestry").segment {
break;
}
reused += 1;
}
if reused != 0 {
parent = Some(Rc::clone(
ancestors[reused - 1].expect("matched cursor prefix"),
));
count!(|c| {
c.cursor_hits += 1;
c.reused_prefix_segments += reused as u64;
});
}
}
}
for segment in &segments[reused..] {
let parent_id = parent.as_ref().map_or(0, |node| Rc::as_ptr(node) as usize);
let key = (parent_id, segment.clone());
let node = match self.entries.get(&key).and_then(Weak::upgrade) {
Some(node) => {
count!(|c| c.pool_hits += 1);
node
}
None => {
count!(|c| c.pool_misses += 1);
if self.entries.len() >= POOL_ENTRY_LIMIT {
self.entries.clear();
count!(|c| c.pool_clears += 1);
}
let node = PathNode::new(parent.clone(), segment.clone());
self.entries.insert(key, Rc::downgrade(&node));
node
}
};
parent = Some(node);
}
if !segments.is_empty() && segments.len() <= INLINE_ITER_DEPTH {
self.cursor_tail = Rc::downgrade(parent.as_ref().expect("nonempty retained path"));
self.cursor_len = segments.len();
} else {
self.cursor_tail = Weak::new();
self.cursor_len = 0;
}
PrefixPath::from_tail(parent, segments.len())
}
pub fn stats(&self) -> PrefixPathPoolStats {
PrefixPathPoolStats {
cursor_weak_entries: usize::from(self.cursor_len != 0),
cursor_dead_entries: usize::from(
self.cursor_len != 0 && self.cursor_tail.strong_count() == 0,
),
cursor_depth: self.cursor_len,
entries: self.entries.len(),
usable_capacity: self.entries.capacity(),
entry_limit: POOL_ENTRY_LIMIT,
dead_entries: self
.entries
.values()
.filter(|node| node.strong_count() == 0)
.count(),
}
}
}
#[cfg(test)]
#[path = "../../tests/private/prefix_path_test.rs"]
mod tests;