oxc_cfg/
lib.rs

1mod block;
2mod builder;
3pub mod dot;
4pub mod visit;
5
6use std::fmt;
7
8use itertools::Itertools;
9use nonmax::NonMaxU32;
10use oxc_index::{Idx, IndexVec};
11use petgraph::{
12    Direction,
13    visit::{Control, DfsEvent, EdgeRef},
14};
15
16pub mod graph {
17    pub use petgraph::*;
18    pub mod visit {
19        pub use petgraph::visit::*;
20
21        pub use super::super::visit::*;
22    }
23}
24
25pub use block::*;
26pub use builder::{ControlFlowGraphBuilder, CtxCursor, CtxFlags};
27pub use dot::DisplayDot;
28use visit::set_depth_first_search;
29
30pub type BlockNodeId = petgraph::stable_graph::NodeIndex;
31#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
32pub struct BasicBlockId(NonMaxU32);
33
34impl Idx for BasicBlockId {
35    #[expect(clippy::cast_possible_truncation)]
36    fn from_usize(idx: usize) -> Self {
37        assert!(idx < u32::MAX as usize);
38        // SAFETY: We just checked `idx` is valid for `NonMaxU32`
39        Self(unsafe { NonMaxU32::new_unchecked(idx as u32) })
40    }
41
42    fn index(self) -> usize {
43        self.0.get() as usize
44    }
45}
46
47impl PartialEq<u32> for BasicBlockId {
48    #[inline]
49    fn eq(&self, other: &u32) -> bool {
50        self.0.get() == *other
51    }
52}
53
54impl fmt::Display for BasicBlockId {
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        self.0.fmt(f)
57    }
58}
59
60pub type Graph = petgraph::graph::DiGraph<BasicBlockId, EdgeType>;
61
62#[derive(Debug, Clone)]
63pub enum EdgeType {
64    /// Conditional jumps
65    Jump,
66    /// Normal control flow path
67    Normal,
68    /// Cyclic aka loops
69    Backedge,
70    /// Marks start of a function subgraph
71    NewFunction,
72    /// Finally
73    Finalize,
74    /// Error Path
75    Error(ErrorEdgeKind),
76
77    // misc edges
78    Unreachable,
79    /// Used to mark the end of a finalizer. It is an experimental approach might
80    /// move to it's respective edge kind enum or get removed altogether.
81    Join,
82}
83
84#[derive(Default, Debug, Clone, Copy)]
85pub enum ErrorEdgeKind {
86    /// Error kind for edges between a block which can throw, to it's respective catch block.
87    Explicit,
88    /// Any block that can throw would have an implicit error block connected using this kind.
89    #[default]
90    Implicit,
91}
92
93pub enum EvalConstConditionResult {
94    NotFound,
95    Fail,
96    Eval(bool),
97}
98
99#[derive(Debug)]
100pub struct ControlFlowGraph {
101    pub graph: Graph,
102    pub basic_blocks: IndexVec<BasicBlockId, BasicBlock>,
103}
104
105impl ControlFlowGraph {
106    pub fn graph(&self) -> &Graph {
107        &self.graph
108    }
109
110    /// # Panics
111    pub fn basic_block(&self, id: BlockNodeId) -> &BasicBlock {
112        let ix = *self.graph.node_weight(id).expect("expected a valid node id in self.graph");
113        self.basic_blocks.get(ix).expect("expected a valid node id in self.basic_blocks")
114    }
115
116    /// # Panics
117    pub fn basic_block_mut(&mut self, id: BlockNodeId) -> &mut BasicBlock {
118        let ix = *self.graph.node_weight(id).expect("expected a valid node id in self.graph");
119        self.basic_blocks.get_mut(ix).expect("expected a valid node id in self.basic_blocks")
120    }
121
122    pub fn is_reachable(&self, from: BlockNodeId, to: BlockNodeId) -> bool {
123        self.is_reachable_filtered(from, to, |_| Control::Continue)
124    }
125
126    pub fn is_reachable_filtered<F: Fn(BlockNodeId) -> Control<bool>>(
127        &self,
128        from: BlockNodeId,
129        to: BlockNodeId,
130        filter: F,
131    ) -> bool {
132        if from == to {
133            return true;
134        }
135        let graph = &self.graph;
136        set_depth_first_search(&self.graph, Some(from), |event| match event {
137            DfsEvent::TreeEdge(a, b) => {
138                let filter_result = filter(a);
139                if !matches!(filter_result, Control::Continue) {
140                    return filter_result;
141                }
142                let unreachable = !graph.edges_connecting(a, b).any(|edge| {
143                    !matches!(edge.weight(), EdgeType::NewFunction | EdgeType::Unreachable)
144                });
145
146                if unreachable {
147                    Control::Prune
148                } else if b == to {
149                    return Control::Break(true);
150                } else {
151                    Control::Continue
152                }
153            }
154            _ => Control::Continue,
155        })
156        .break_value()
157        .unwrap_or(false)
158    }
159
160    /// Returns `None` the given node isn't the cyclic point of an infinite loop.
161    /// Otherwise returns `Some(loop_start, loop_end)`.
162    ///
163    /// # Panics
164    ///
165    /// * There should only be one backedge to each basic block.
166    pub fn is_infinite_loop_start<F>(
167        &self,
168        node: BlockNodeId,
169        try_eval_const_condition: F,
170    ) -> Option<(BlockNodeId, BlockNodeId)>
171    where
172        F: Fn(&Instruction) -> EvalConstConditionResult,
173    {
174        fn get_jump_target(graph: &Graph, node: BlockNodeId) -> Option<BlockNodeId> {
175            graph
176                .edges_directed(node, Direction::Outgoing)
177                .find_or_first(|e| matches!(e.weight(), EdgeType::Jump))
178                .map(|it| it.target())
179        }
180
181        let basic_block = self.basic_block(node);
182        let mut backedges = self
183            .graph
184            .edges_directed(node, Direction::Incoming)
185            .filter(|e| matches!(e.weight(), EdgeType::Backedge));
186
187        // if this node doesn't have an backedge it isn't a loop starting point.
188        let backedge = backedges.next()?;
189
190        assert!(
191            backedges.next().is_none(),
192            "there should only be one backedge to each basic block."
193        );
194
195        // if instructions are empty we might be in a `for(;;)`.
196        if basic_block.instructions().is_empty()
197            && !self
198                .graph
199                .edges_directed(node, Direction::Outgoing)
200                .any(|e| matches!(e.weight(), EdgeType::Backedge))
201        {
202            return get_jump_target(&self.graph, node).map(|it| (it, node));
203        }
204
205        // if there are more than one instruction in this block it can't be a valid loop start.
206        let Ok(only_instruction) = basic_block.instructions().iter().exactly_one() else {
207            return None;
208        };
209
210        // if there is exactly one and it is a condition instruction we are in a loop so we
211        // check the condition to infer if it is always true.
212        if matches!(
213            try_eval_const_condition(only_instruction),
214            EvalConstConditionResult::Eval(true)
215        ) {
216            get_jump_target(&self.graph, node).map(|it| (it, node))
217        } else if matches!(
218            self.basic_block(backedge.source())
219                .instructions()
220                .iter()
221                .exactly_one()
222                .map_or_else(|_| EvalConstConditionResult::NotFound, try_eval_const_condition),
223            EvalConstConditionResult::Eval(true)
224        ) {
225            get_jump_target(&self.graph, node).map(|it| (node, it))
226        } else {
227            None
228        }
229    }
230
231    pub fn is_cyclic(&self, node: BlockNodeId) -> bool {
232        set_depth_first_search(&self.graph, Some(node), |event| match event {
233            DfsEvent::BackEdge(_, id) if id == node => Err(()),
234            _ => Ok(()),
235        })
236        .is_err()
237    }
238}
oxc_cfg/lib.rs

oxc_cfg/
lib.rs
