rustc_middle/dep_graph/
edges.rs

1//! How a task's reads are recorded and deduplicated into the edge list of its node.
2
3use rustc_data_structures::fx::FxHashSet;
4use rustc_data_structures::sync::Lock;
5
6use super::DepNodeIndex;
7
8/// How many reads fit in [`TaskReads::Small`]'s inline buffer.
9pub(crate) const SMALL_READS_MAX: usize = 16;
10
11/// The reads recorded by one task so far, deduplicated and in first-read order.
12#[derive(#[automatically_derived]
impl ::core::fmt::Debug for TaskReads {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        match self {
            TaskReads::Small { len: __self_0, buf: __self_1 } =>
                ::core::fmt::Formatter::debug_struct_field2_finish(f, "Small",
                    "len", __self_0, "buf", &__self_1),
            TaskReads::Recorded(__self_0) =>
                ::core::fmt::Formatter::debug_tuple_field1_finish(f,
                    "Recorded", &__self_0),
        }
    }
}Debug)]
13pub(crate) enum TaskReads {
14    /// The first few reads, deduplicated by a linear scan. Most tasks never outgrow this.
15    Small { len: u8, buf: [DepNodeIndex; SMALL_READS_MAX] },
16
17    /// The reads of a task that outgrew the inline buffer.
18    Recorded(ReadsRecorder),
19}
20
21impl TaskReads {
22    #[inline]
23    pub(crate) fn new() -> Self {
24        TaskReads::Small { len: 0, buf: [DepNodeIndex::ZERO; SMALL_READS_MAX] }
25    }
26
27    /// Records a read and returns whether it was new for the task. The pool provides a
28    /// recorder when the task outgrows the inline buffer.
29    #[inline]
30    pub(crate) fn insert(&mut self, index: DepNodeIndex, pool: &Lock<Vec<ReadsRecorder>>) -> bool {
31        match self {
32            TaskReads::Recorded(recorder) => recorder.insert(index),
33            TaskReads::Small { len, buf } => {
34                let n = usize::from(*len);
35                if buf[..n].contains(&index) {
36                    false
37                } else if n < SMALL_READS_MAX {
38                    buf[n] = index;
39                    *len += 1;
40                    true
41                } else {
42                    // The inline buffer is full: move the reads into a pooled recorder.
43                    let seed = *buf;
44                    let mut recorder = pool.lock().pop().unwrap_or_default();
45                    recorder.clear();
46                    recorder.seed(&seed);
47                    recorder.insert(index);
48                    *self = TaskReads::Recorded(recorder);
49                    true
50                }
51            }
52        }
53    }
54
55    /// The task's deduplicated reads, in first-read order.
56    #[inline]
57    pub(crate) fn edges(&self) -> &[DepNodeIndex] {
58        match self {
59            TaskReads::Small { len, buf } => &buf[..usize::from(*len)],
60            TaskReads::Recorded(recorder) => &recorder.reads,
61        }
62    }
63}
64
65/// Records the reads of a task with many reads.
66///
67/// Recorders are pooled globally, reusing the read list and hash set allocations
68/// across tasks.
69#[derive(#[automatically_derived]
impl ::core::fmt::Debug for ReadsRecorder {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field2_finish(f, "ReadsRecorder",
            "reads", &self.reads, "seen", &&self.seen)
    }
}Debug, #[automatically_derived]
impl ::core::default::Default for ReadsRecorder {
    #[inline]
    fn default() -> ReadsRecorder {
        ReadsRecorder {
            reads: ::core::default::Default::default(),
            seen: ::core::default::Default::default(),
        }
    }
}Default)]
70pub(crate) struct ReadsRecorder {
71    /// The deduplicated reads, in first-read order.
72    reads: Vec<DepNodeIndex>,
73    seen: FxHashSet<DepNodeIndex>,
74}
75
76impl ReadsRecorder {
77    /// Seeds a fresh recorder with reads that are already known to be distinct.
78    fn seed(&mut self, reads: &[DepNodeIndex]) {
79        if true {
    if !self.reads.is_empty() {
        ::core::panicking::panic("assertion failed: self.reads.is_empty()")
    };
};debug_assert!(self.reads.is_empty());
80        self.seen.extend(reads);
81        self.reads.extend_from_slice(reads);
82    }
83
84    /// Records a read of `index` and returns whether it was new for the current task.
85    #[inline]
86    fn insert(&mut self, index: DepNodeIndex) -> bool {
87        let new = self.seen.insert(index);
88        if new {
89            self.reads.push(index);
90        }
91        new
92    }
93
94    /// Prepares the recorder for a new task, keeping the backing allocations.
95    fn clear(&mut self) {
96        self.reads.clear();
97        self.seen.clear();
98    }
99
100    /// Returns a finished task's recorder to the pool. The cap keeps deeply nested tasks
101    /// from growing the pool without bound.
102    #[inline]
103    pub(crate) fn release(self, pool: &Lock<Vec<ReadsRecorder>>) {
104        const MAX_POOLED_RECORDERS: usize = 4;
105        let mut pool = pool.lock();
106        if pool.len() < MAX_POOLED_RECORDERS {
107            pool.push(self);
108        }
109    }
110}
rustc_middle/dep_graph/edges.rs

rustc_middle/dep_graph/
edges.rs
