gbf_core/decompiler/structure_analysis/
region.rs

1#![deny(missing_docs)]
2
3use crate::cfg_dot::RenderableNode;
4use crate::decompiler::ast::AstKind;
5use crate::decompiler::ast::expr::ExprKind;
6use crate::decompiler::ast::visitors::AstVisitor;
7use crate::decompiler::ast::visitors::emit_context::{EmitContextBuilder, EmitVerbosity};
8use crate::decompiler::ast::visitors::emitter::Gs2Emitter;
9use crate::opcode::Opcode;
10use crate::utils::{GBF_GREEN, GBF_YELLOW, html_encode};
11use serde::{Deserialize, Serialize};
12use std::fmt::{Display, Write};
13use std::slice::Iter;
14
15/// Represents the type of control-flow region.
16#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize, Copy)]
17pub enum RegionType {
18    /// Simply moves on to the next region without control flow
19    Linear,
20    /// Control flow construct (e.g. for, while, if, switch, etc.)
21    ControlFlow,
22    /// A tail (e.g, return)
23    Tail,
24    /// A region that is inactive and removed from the graph from structure analysis
25    Inactive,
26}
27
28/// Describes a region
29#[derive(Debug, Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize, Copy)]
30pub struct RegionId {
31    /// The index of the region
32    pub index: usize,
33}
34
35impl Display for RegionId {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        write!(f, "RegionId({})", self.index)
38    }
39}
40
41impl RegionId {
42    /// Create a new `RegionId`.
43    ///
44    /// # Arguments
45    /// - `index`: The index of the region in the graph.
46    ///
47    /// # Returns
48    /// - A new `RegionId` instance.
49    pub fn new(index: usize) -> Self {
50        Self { index }
51    }
52}
53
54/// Represents a region in the control-flow graph.
55#[derive(Debug, Clone)]
56pub struct Region {
57    nodes: Vec<AstKind>,
58    unresolved_nodes: Vec<AstKind>,
59    jump_expr: Option<ExprKind>,
60    region_type: RegionType,
61    branch_opcode: Option<Opcode>,
62    region_id: RegionId,
63}
64
65impl Region {
66    /// Creates a new region with the specified type and initializes with no statements.
67    ///
68    /// # Arguments
69    /// * `id` - The id of the region.
70    pub fn new(region_type: RegionType, region_id: RegionId) -> Self {
71        Self {
72            nodes: Vec::new(),
73            unresolved_nodes: Vec::new(),
74            jump_expr: None,
75            region_type,
76            branch_opcode: None,
77            region_id,
78        }
79    }
80
81    /// Returns the type of the region.
82    pub fn region_type(&self) -> &RegionType {
83        &self.region_type
84    }
85
86    /// Adds a statement to the region.
87    ///
88    /// # Arguments
89    /// * `node` - The AST node to add.
90    pub fn push_node(&mut self, node: AstKind) {
91        self.nodes.push(node);
92    }
93
94    /// Adds an unresolved statement to the region.
95    ///
96    /// # Arguments
97    /// * `node` - The AST node to add.
98    pub fn push_unresolved_node(&mut self, node: AstKind) {
99        self.unresolved_nodes.push(node);
100    }
101
102    /// Adds multiple statements to the region.
103    ///
104    /// # Arguments
105    /// * `nodes` - The AST nodes to add.
106    pub fn push_nodes(&mut self, nodes: Vec<AstKind>) {
107        self.nodes.extend(nodes);
108    }
109
110    /// Adds multiple unresolved statements to the region.
111    ///
112    /// # Arguments
113    /// * `nodes` - The AST nodes to add.
114    pub fn push_unresolved_nodes(&mut self, nodes: Vec<AstKind>) {
115        self.unresolved_nodes.extend(nodes);
116    }
117
118    /// Clears the nodes in the region
119    pub fn clear_nodes(&mut self) {
120        self.nodes.clear();
121    }
122
123    /// Clears the unresolved nodes in the region
124    pub fn clear_unresolved_nodes(&mut self) {
125        self.unresolved_nodes.clear();
126    }
127
128    /// Gets the nodes in the region.
129    ///
130    /// # Return
131    /// The nodes in the region.
132    pub fn get_nodes(&self) -> &Vec<AstKind> {
133        &self.nodes
134    }
135
136    /// Gets the unresolved nodes in the region.
137    ///
138    /// # Return
139    /// The unresolved nodes in the region.
140    pub fn get_unresolved_nodes(&self) -> &Vec<AstKind> {
141        &self.unresolved_nodes
142    }
143
144    /// Gets the region type.
145    ///
146    /// # Return
147    /// The region type.
148    pub fn get_region_type(&self) -> RegionType {
149        self.region_type
150    }
151
152    /// Sets the type of the region.
153    ///
154    /// # Arguments
155    /// * `region_type` - The new type of the region.
156    pub fn set_region_type(&mut self, region_type: RegionType) {
157        self.region_type = region_type;
158    }
159
160    /// Remove the jump expression from the region.
161    pub fn remove_jump_expr(&mut self) {
162        self.jump_expr = None;
163    }
164
165    /// Gets the jump expression.
166    ///
167    /// # Return
168    /// The jump expression.
169    pub fn get_jump_expr(&self) -> Option<&ExprKind> {
170        self.jump_expr.as_ref()
171    }
172
173    /// Sets the jump expression.
174    ///
175    /// # Arguments
176    /// * `jump_expr` - The new optional jump expression.
177    pub fn set_jump_expr(&mut self, jump_expr: Option<ExprKind>) {
178        self.jump_expr = jump_expr;
179    }
180
181    /// Gets the branch opcode, if any.
182    ///
183    /// # Return
184    /// The opcode.
185    pub fn get_branch_opcode(&self) -> Option<Opcode> {
186        self.branch_opcode
187    }
188
189    /// Sets the opcode.
190    ///
191    /// # Arguments
192    /// * `opcode` - The new opcode.
193    pub fn set_branch_opcode(&mut self, opcode: Opcode) {
194        self.branch_opcode = Some(opcode);
195    }
196
197    /// Returns an iterator over the statements in the region.
198    ///
199    /// # Return
200    /// An iterator over the statements in the region.
201    pub fn iter_nodes(&self) -> Iter<AstKind> {
202        self.nodes.iter()
203    }
204}
205
206// === Other Implementations ===
207
208/// Allows iterating over the statements in a region.
209impl<'a> IntoIterator for &'a Region {
210    type Item = &'a AstKind;
211    type IntoIter = Iter<'a, AstKind>;
212
213    fn into_iter(self) -> Self::IntoIter {
214        self.nodes.iter()
215    }
216}
217
218/// Allows iterating over the statements in a region (mutable).
219impl<'a> IntoIterator for &'a mut Region {
220    type Item = &'a mut AstKind;
221    type IntoIter = std::slice::IterMut<'a, AstKind>;
222
223    fn into_iter(self) -> Self::IntoIter {
224        self.nodes.iter_mut()
225    }
226}
227
228impl RenderableNode for Region {
229    /// Render the region's node representation for Graphviz with customizable padding.
230    ///
231    /// # Arguments
232    /// * `padding` - The number of spaces to use for indentation.
233    ///
234    /// # Return
235    /// The rendered node
236    fn render_node(&self, padding: usize) -> String {
237        let mut label = String::new();
238        let indent = " ".repeat(padding);
239
240        // Start the HTML-like table for Graphviz.
241        writeln!(
242            &mut label,
243            r#"{indent}<TABLE BORDER="0" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0">"#,
244            indent = indent
245        )
246        .unwrap();
247
248        // Write RegionId
249        writeln!(
250            &mut label,
251            r#"{indent}<TR><TD ALIGN="LEFT"><FONT COLOR="{GBF_GREEN}">{}</FONT></TD></TR><TR><TD> </TD></TR>"#,
252            html_encode(format!("{}", self.region_id)),
253            GBF_GREEN = GBF_GREEN,
254            indent = indent
255        ).unwrap();
256
257        // Write the region type as the label.
258        let region_type_str = match self.region_type {
259            RegionType::Linear => "Linear",
260            RegionType::ControlFlow => "ControlFlow",
261            RegionType::Tail => "Tail",
262            RegionType::Inactive => "Inactive",
263        };
264        writeln!(
265            &mut label,
266            r#"{indent}<TR><TD ALIGN="LEFT"><FONT COLOR="{GBF_GREEN}">RegionType: {}</FONT></TD></TR><TR><TD> </TD></TR>"#,
267            region_type_str,
268            GBF_GREEN = GBF_GREEN,
269            indent = indent
270        )
271        .unwrap();
272
273        // Render each statement as a table row with indentation.
274        for node in &self.nodes {
275            // Build a new EmitContext with debug
276            let context = EmitContextBuilder::default()
277                .verbosity(EmitVerbosity::Debug)
278                .include_ssa_versions(true)
279                .build();
280            let mut emitter = Gs2Emitter::new(context);
281            let result = emitter.visit_node(node).node;
282
283            // split the result by newlines
284            let result = result.split('\n').collect::<Vec<&str>>();
285
286            for line in result {
287                writeln!(
288                    &mut label,
289                    r#"{indent}<TR><TD ALIGN="LEFT"><FONT COLOR="{GBF_YELLOW}">{}</FONT></TD></TR>"#,
290                    html_encode(line),
291                    GBF_YELLOW = GBF_YELLOW,
292                    indent = indent
293                )
294                .unwrap();
295            }
296        }
297
298        // If the region has a condition, render it.
299        if let Some(jump_expr) = &self.jump_expr {
300            // Build a new EmitContext with debug
301            let context = EmitContextBuilder::default()
302                .verbosity(EmitVerbosity::Pretty)
303                .include_ssa_versions(true)
304                .build();
305            let mut emitter = Gs2Emitter::new(context);
306            let result = emitter.visit_expr(jump_expr);
307
308            writeln!(
309                &mut label,
310                r##"{indent}    <TR><TD> </TD></TR><TR>
311{indent}        <TD ALIGN="LEFT"><FONT COLOR="{GBF_GREEN}">JumpExpr: {}</FONT></TD>
312{indent}    </TR>"##,
313                html_encode(result.node),
314                GBF_GREEN = GBF_GREEN,
315                indent = indent
316            )
317            .unwrap();
318        }
319
320        // Close the HTML-like table.
321        writeln!(&mut label, "{indent}</TABLE>", indent = indent).unwrap();
322
323        label
324    }
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330    use crate::decompiler::ast::{bin_op::BinOpType, new_assignment, new_bin_op, new_id, new_num};
331
332    #[test]
333    fn test_region_creation_and_instruction_addition() {
334        let mut region = Region::new(RegionType::Linear, RegionId::new(0));
335
336        assert_eq!(region.region_type(), &RegionType::Linear);
337        assert_eq!(region.iter_nodes().count(), 0);
338
339        let ast_node1 = new_assignment(
340            new_id("x"),
341            new_bin_op(new_num(1), new_num(2), BinOpType::Add).unwrap(),
342        );
343
344        let ast_node2 = new_assignment(
345            new_id("y"),
346            new_bin_op(new_num(3), new_num(4), BinOpType::Sub).unwrap(),
347        );
348
349        region.push_node(ast_node1.clone().into());
350        region.push_node(ast_node2.clone().into());
351
352        let mut iter = region.iter_nodes();
353        assert_eq!(iter.next(), Some(&ast_node1.clone().into()));
354        assert_eq!(iter.next(), Some(&ast_node2.clone().into()));
355    }
356
357    #[test]
358    fn test_region_into_iter() {
359        let region = Region::new(RegionType::Linear, RegionId::new(1));
360        let mut iter = region.into_iter();
361        assert_eq!(iter.next(), None);
362    }
363}
gbf_core/decompiler/structure_analysis/region.rs

gbf_core/decompiler/structure_analysis/
region.rs
