rustc_monomorphize/graph_checks/
statics.rs

1use rustc_data_structures::fx::FxIndexSet;
2use rustc_data_structures::graph::scc::Sccs;
3use rustc_data_structures::graph::{DirectedGraph, Successors};
4use rustc_data_structures::unord::UnordMap;
5use rustc_hir::def_id::DefId;
6use rustc_index::{Idx, IndexVec, newtype_index};
7use rustc_middle::mir::mono::MonoItem;
8use rustc_middle::ty::TyCtxt;
9
10use crate::collector::UsageMap;
11use crate::errors;
12
13#[derive(#[automatically_derived]
impl ::core::clone::Clone for StaticNodeIdx {
    #[inline]
    fn clone(&self) -> StaticNodeIdx {
        let _: ::core::clone::AssertParamIsClone<usize>;
        *self
    }
}Clone, #[automatically_derived]
impl ::core::marker::Copy for StaticNodeIdx { }Copy, #[automatically_derived]
impl ::core::fmt::Debug for StaticNodeIdx {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_tuple_field1_finish(f, "StaticNodeIdx",
            &&self.0)
    }
}Debug, #[automatically_derived]
impl ::core::cmp::Eq for StaticNodeIdx {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_receiver_is_total_eq(&self) -> () {
        let _: ::core::cmp::AssertParamIsEq<usize>;
    }
}Eq, #[automatically_derived]
impl ::core::hash::Hash for StaticNodeIdx {
    #[inline]
    fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) -> () {
        ::core::hash::Hash::hash(&self.0, state)
    }
}Hash, #[automatically_derived]
impl ::core::cmp::PartialEq for StaticNodeIdx {
    #[inline]
    fn eq(&self, other: &StaticNodeIdx) -> bool { self.0 == other.0 }
}PartialEq)]
14struct StaticNodeIdx(usize);
15
16impl Idx for StaticNodeIdx {
17    fn new(idx: usize) -> Self {
18        Self(idx)
19    }
20
21    fn index(self) -> usize {
22        self.0
23    }
24}
25
26impl From<usize> for StaticNodeIdx {
27    fn from(value: usize) -> Self {
28        StaticNodeIdx(value)
29    }
30}
31
32impl ::std::fmt::Debug for StaticSccIdx {
    fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
        fmt.write_fmt(format_args!("{0}", self.as_u32()))
    }
}newtype_index! {
33    #[derive(Ord, PartialOrd)]
34    struct StaticSccIdx {}
35}
36
37// Adjacency-list graph for statics using `StaticNodeIdx` as node type.
38// We cannot use `DefId` as the node type directly because each node must be
39// represented by an index in the range `0..num_nodes`.
40struct StaticRefGraph<'a, 'b, 'tcx> {
41    // maps from `StaticNodeIdx` to `DefId` and vice versa
42    statics: &'a FxIndexSet<DefId>,
43    // contains for each `MonoItem` the `MonoItem`s it uses
44    used_map: &'b UnordMap<MonoItem<'tcx>, Vec<MonoItem<'tcx>>>,
45}
46
47impl<'a, 'b, 'tcx> DirectedGraph for StaticRefGraph<'a, 'b, 'tcx> {
48    type Node = StaticNodeIdx;
49
50    fn num_nodes(&self) -> usize {
51        self.statics.len()
52    }
53}
54
55impl<'a, 'b, 'tcx> Successors for StaticRefGraph<'a, 'b, 'tcx> {
56    fn successors(&self, node_idx: StaticNodeIdx) -> impl Iterator<Item = StaticNodeIdx> {
57        let def_id = self.statics[node_idx.index()];
58        self.used_map[&MonoItem::Static(def_id)].iter().filter_map(|&mono_item| match mono_item {
59            MonoItem::Static(def_id) => self.statics.get_index_of(&def_id).map(|idx| idx.into()),
60            _ => None,
61        })
62    }
63}
64
65pub(super) fn check_static_initializers_are_acyclic<'tcx, 'a, 'b>(
66    tcx: TyCtxt<'tcx>,
67    mono_items: &'a [MonoItem<'tcx>],
68    usage_map: &'b UsageMap<'tcx>,
69) {
70    // Collect statics
71    let statics: FxIndexSet<DefId> = mono_items
72        .iter()
73        .filter_map(|&mono_item| match mono_item {
74            MonoItem::Static(def_id) => Some(def_id),
75            _ => None,
76        })
77        .collect();
78
79    // If we don't have any statics the check is not necessary
80    if statics.is_empty() {
81        return;
82    }
83    // Create a subgraph from the mono item graph, which only contains statics
84    let graph = StaticRefGraph { statics: &statics, used_map: &usage_map.used_map };
85    // Calculate its SCCs
86    let sccs: Sccs<StaticNodeIdx, StaticSccIdx> = Sccs::new(&graph);
87    // Group statics by SCCs
88    let mut nodes_of_sccs: IndexVec<StaticSccIdx, Vec<StaticNodeIdx>> =
89        IndexVec::from_elem_n(Vec::new(), sccs.num_sccs());
90    for i in graph.iter_nodes() {
91        nodes_of_sccs[sccs.scc(i)].push(i);
92    }
93    let is_cyclic = |nodes_of_scc: &[StaticNodeIdx]| -> bool {
94        match nodes_of_scc.len() {
95            0 => false,
96            1 => graph.successors(nodes_of_scc[0]).any(|x| x == nodes_of_scc[0]),
97            2.. => true,
98        }
99    };
100    // Emit errors for all cycles
101    for nodes in nodes_of_sccs.iter_mut().filter(|nodes| is_cyclic(nodes)) {
102        // We sort the nodes by their Span to have consistent error line numbers
103        nodes.sort_by_key(|node| tcx.def_span(statics[node.index()]));
104
105        let head_def = statics[nodes[0].index()];
106        let head_span = tcx.def_span(head_def);
107
108        tcx.dcx().emit_err(errors::StaticInitializerCyclic {
109            span: head_span,
110            labels: nodes.iter().map(|&n| tcx.def_span(statics[n.index()])).collect(),
111            head: &tcx.def_path_str(head_def),
112            target: &tcx.sess.target.llvm_target,
113        });
114    }
115}
rustc_monomorphize/graph_checks/statics.rs

rustc_monomorphize/graph_checks/
statics.rs
