Skip to main content

decl_lang/semantics/
prefix_path.rs

1//! Experimental retained container paths. Flat `SegPath` remains the interchange
2//! representation; no flattened vector is cached in a retained path.
3use 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/// Thread-local, cumulative diagnostics for the representation experiment.
15/// Live counts include all owners on this thread, including external API owners;
16/// take before/after snapshots instead of resetting counters under live paths.
17#[derive(Clone, Copy, Debug, Default)]
18#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
19pub struct PrefixPathDiagnostics {
20    /// Calls to the engine pool, including empty and deep paths.
21    pub retain_calls: u64,
22    /// Total input segments passed to the engine pool.
23    pub input_segments: u64,
24    /// Bounded nonempty inputs for which a previous weak cursor was available.
25    /// Includes attempts whose weak tail had already expired.
26    pub cursor_attempts: u64,
27    /// Cursor attempts that reused at least one canonical prefix segment.
28    pub cursor_hits: u64,
29    /// Prefix segments reused without a hash-table lookup.
30    pub reused_prefix_segments: u64,
31    /// Inputs beyond the inline cursor depth; these use the original full lookup.
32    pub cursor_deep_fallbacks: u64,
33    /// Retained path bodies constructed, including non-Rc public values.
34    pub handles_created: u64,
35    /// Retained path bodies whose destructor has not run.
36    pub handles_live: u64,
37    /// Prefix nodes allocated by pool and direct constructors.
38    pub nodes_created: u64,
39    /// Prefix nodes with a strong owner; excludes weak-only reserved storage.
40    pub nodes_live: u64,
41    /// Maximum strongly live node count observed on this thread.
42    pub nodes_peak: u64,
43    /// Pool lookups that upgraded an existing prefix node.
44    pub pool_hits: u64,
45    /// Pool lookups that allocated a prefix node.
46    pub pool_misses: u64,
47    /// Whole bounded-pool clears before new insertions.
48    pub pool_clears: u64,
49    /// Explicit to_vec exports; no export is cached by PrefixPath.
50    pub flat_exports: u64,
51    /// Total segment count requested by explicit flat exports.
52    pub flat_export_segments: u64,
53    /// Borrowed iterators whose ancestry exceeded inline storage.
54    pub iterator_spills: u64,
55}
56
57#[cfg(feature = "runtime-diagnostics")]
58thread_local! {
59    static COUNTERS: Cell<PrefixPathDiagnostics> = Cell::new(PrefixPathDiagnostics::default());
60}
61
62// Remove the whole counter expression, including closure creation and its
63// captured operands, from feature-empty primary builds.
64macro_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    // Paths may be destroyed during thread-local teardown; diagnostics must not
76    // turn their otherwise valid destruction into a panic.
77    let _ = COUNTERS.try_with(|cell| {
78        let mut counters = cell.get();
79        f(&mut counters);
80        cell.set(counters);
81    });
82}
83
84/// Read cumulative diagnostics on the calling thread. Feature-empty builds
85/// return zeros and compile out the counter TLS and all hot counter calls.
86pub 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/// Concrete layouts, excluding allocator rounding. The Rc header estimate is
98/// explicit so a requested-allocation probe can verify it for its toolchain.
99#[derive(Clone, Copy, Debug)]
100#[cfg_attr(feature = "runtime-diagnostics", derive(serde::Serialize))]
101pub struct PrefixPathLayouts {
102    /// Inline PrefixPath body size, excluding its optional outer Rc allocation.
103    pub path_body: usize,
104    /// Inline immutable node body size, excluding Rc counts.
105    pub node_body: usize,
106    /// Key and weak value payload size; excludes hash control/capacity overhead.
107    pub pool_entry: usize,
108    /// Pool struct size, excluding its hash allocation.
109    pub pool_body: usize,
110    /// Iterator stack body size, excluding a deep ancestry spill.
111    pub iterator_body: usize,
112    /// Two word-sized Rc counts; verify requested allocation layout separately.
113    pub assumed_rc_header: usize,
114}
115
116/// Report this compiled prototype's representation layouts.
117pub 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        // Release a uniquely owned chain iteratively. Path depth must not turn
148        // a valid public API value into a recursive-drop stack overflow.
149        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
159/// A retained path with immutable shared prefixes and a unique outer handle.
160/// `iter` borrows segments; `to_vec` is an explicit temporary flat export.
161/// Public mutation creates a new tail, preserving other cloned path snapshots.
162pub 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    /// Construct without a pool. Use `Engine::retained_path` to share prefixes
177    /// across independently constructed container paths in one engine.
178    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    /// Number of canonical segments.
187    pub fn len(&self) -> usize {
188        self.len
189    }
190
191    /// Whether this path has no segments.
192    pub fn is_empty(&self) -> bool {
193        self.len == 0
194    }
195
196    /// Borrow the root segment, walking its ancestry.
197    pub fn first(&self) -> Option<&Seg> {
198        self.get(0)
199    }
200
201    /// Borrow the tail segment in constant time.
202    pub fn last(&self) -> Option<&Seg> {
203        self.tail.as_deref().map(|node| &node.segment)
204    }
205
206    /// Indexed lookup walks backwards from the tail. Sequential consumers
207    /// should use `iter`, which constructs its borrowed traversal once.
208    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    /// Borrow segments in canonical order; deep paths use temporary references.
220    pub fn iter(&self) -> PrefixPathIter<'_> {
221        PrefixPathIter::new(self)
222    }
223
224    /// Format through the same canonical spelling as `path_str`, borrowing
225    /// segments and retaining no flat vector.
226    pub fn format(&self, rel_root: Option<&str>) -> String {
227        super::path_str_iter(self.iter(), rel_root)
228    }
229
230    /// Export an owned flat path and record the explicit conversion.
231    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        // One exact requested buffer, O(depth), no retained flat cache and no
237        // iterator spill allocation even for unusually deep public API paths.
238        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    /// Append without changing any shared prefix node.
249    pub fn push(&mut self, segment: Seg) {
250        self.tail = Some(PathNode::new(self.tail.take(), segment));
251        self.len += 1;
252    }
253
254    /// Remove the tail without modifying any shared prefix node.
255    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    /// Release this body's ancestry without changing other snapshots.
264    pub fn clear(&mut self) {
265        self.tail = None;
266        self.len = 0;
267    }
268
269    /// Borrowed ancestry identity for an external diagnostic only. This is not
270    /// a stable language identity, and does not identify a reference snapshot.
271    pub fn prefix_node_ids(&self) -> impl Iterator<Item = usize> + '_ {
272        self.prefix_nodes().map(|(id, _)| id)
273    }
274
275    /// Tail-to-root borrowed nodes for a deduplicating owner census. The tuple
276    /// exposes each node's segment owner without cloning or flattening paths.
277    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
326/// Forward/backward borrowed traversal. Depth <= 16 allocates nothing; deeper
327/// paths allocate a temporary vector of node references, never cloned Segs.
328pub 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/// A bounded accelerator for sharing existing prefixes, not a semantic cache.
414/// Weak entries do not retain path bodies; clearing never invalidates a path.
415#[derive(Default)]
416pub struct PrefixPathPool {
417    entries: FxHashMap<(usize, Seg), Weak<PathNode>>,
418    // Never keep an outer path or a strong node owner in this accelerator.
419    cursor_tail: Weak<PathNode>,
420    cursor_len: usize,
421}
422
423/// Explicit bounded-pool occupancy and weak-storage diagnostic.
424#[derive(Clone, Copy, Debug)]
425pub struct PrefixPathPoolStats {
426    /// Zero or one additional weak node references held by the ancestry cursor.
427    /// This can refer to the same allocation as a hash-table entry.
428    pub cursor_weak_entries: usize,
429    /// Cursor weak references whose node body has died. Not an additional unique
430    /// allocation count: the hash table can also hold the same dead allocation.
431    pub cursor_dead_entries: usize,
432    /// Cached path depth, zero when empty and never greater than 16.
433    pub cursor_depth: usize,
434    /// Weak entries currently retained by this pool.
435    pub entries: usize,
436    /// HashMap usable capacity, not allocator bytes or physical bucket count.
437    pub usable_capacity: usize,
438    /// Maximum entries before the next insertion clears the pool.
439    pub entry_limit: usize,
440    /// Weak entries whose node body has died but allocation remains reserved.
441    pub dead_entries: usize,
442}
443
444impl PrefixPathPool {
445    /// Retain a distinct outer path handle with any locally shared prefixes.
446    pub fn retain(&mut self, segments: &[Seg]) -> Rc<PrefixPath> {
447        Rc::new(self.retain_value(segments))
448    }
449
450    /// Retain a path value with shared prefixes, without an outer allocation.
451    /// Cloning or mutating the returned handle leaves other handles independent.
452    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                // The temporary tail owner keeps these borrowed Rc references
465                // valid. No flattened Seg vector or persistent strong owner.
466                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                    // A successful upgrade pins this node's strong parent,
498                    // hence its parent's address cannot have been recycled.
499                    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        // Never intern the outer Rc: snapshot reference identity is a separate
523        // concern even if the representation is later adopted for references.
524        PrefixPath::from_tail(parent, segments.len())
525    }
526
527    /// O(entry count), explicitly requested diagnostics; absent from binding.
528    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;