gbf_core/decompiler/structure_analysis/
cyclic_region_reducer.rs

1#![deny(missing_docs)]
2
3use std::backtrace::Backtrace;
4
5use crate::decompiler::ast::{
6    AstKind, control_flow::ControlFlowNode, expr::ExprKind, new_cyclic_condition, new_do_while,
7    ptr::P,
8};
9
10use super::{
11    RegionReducer, StructureAnalysis, StructureAnalysisError,
12    region::{RegionId, RegionType},
13};
14
15/// Reduces a linear region.
16pub struct CyclicRegionReducer;
17
18impl CyclicRegionReducer {
19    /// Extracts the jump expression from a region, if available.
20    fn extract_jump_expr(
21        analysis: &mut StructureAnalysis,
22        region_id: RegionId,
23    ) -> Result<ExprKind, StructureAnalysisError> {
24        let region = analysis.regions.get_mut(region_id.index).ok_or(
25            StructureAnalysisError::RegionNotFound {
26                region_id,
27                backtrace: Backtrace::capture(),
28            },
29        )?;
30        region
31            .get_jump_expr()
32            .ok_or(StructureAnalysisError::ExpectedConditionNotFound {
33                backtrace: Backtrace::capture(),
34            })
35            .cloned()
36    }
37
38    /// Remove the given node and its adjacent edges from the region.
39    fn cleanup_region(
40        analysis: &mut StructureAnalysis,
41        remove_node: RegionId,
42        start_node: RegionId,
43        final_node: RegionId,
44    ) -> Result<(), StructureAnalysisError> {
45        analysis.remove_edge(start_node, remove_node)?;
46        analysis.remove_edge(remove_node, final_node)?;
47        analysis.remove_node(remove_node)?;
48        Ok(())
49    }
50
51    /// Handles merging the conditional structure into the original region.
52    fn merge_conditional(
53        analysis: &mut StructureAnalysis,
54        region_id: RegionId,
55        cond: P<ControlFlowNode>,
56    ) -> Result<(), StructureAnalysisError> {
57        let region = analysis.regions.get_mut(region_id.index).ok_or(
58            StructureAnalysisError::RegionNotFound {
59                region_id,
60                backtrace: Backtrace::capture(),
61            },
62        )?;
63        region.push_node(cond.into());
64        region.set_region_type(RegionType::Linear);
65        region.remove_jump_expr();
66        Ok(())
67    }
68
69    /// Replace the region nodes with the given nodes (for do-while loops).
70    fn replace_region_nodes(
71        analysis: &mut StructureAnalysis,
72        region_id: RegionId,
73        node: P<ControlFlowNode>,
74    ) -> Result<(), StructureAnalysisError> {
75        let region = analysis.regions.get_mut(region_id.index).ok_or(
76            StructureAnalysisError::RegionNotFound {
77                region_id,
78                backtrace: Backtrace::capture(),
79            },
80        )?;
81        region.clear_nodes();
82        region.push_node(node.into());
83        region.set_region_type(RegionType::Linear);
84        region.remove_jump_expr();
85
86        // Remove edge between the region and itself
87        analysis.remove_edge(region_id, region_id)?;
88        Ok(())
89    }
90
91    /// Extracts the nodes of a given region.
92    fn get_region_nodes(
93        analysis: &StructureAnalysis,
94        region_id: RegionId,
95    ) -> Result<Vec<AstKind>, StructureAnalysisError> {
96        let region = analysis.regions.get(region_id.index).ok_or(
97            StructureAnalysisError::RegionNotFound {
98                region_id,
99                backtrace: Backtrace::capture(),
100            },
101        )?;
102        Ok(region.get_nodes().to_vec())
103    }
104}
105
106impl RegionReducer for CyclicRegionReducer {
107    fn reduce_region(
108        &mut self,
109        analysis: &mut StructureAnalysis,
110        region_id: RegionId,
111    ) -> Result<bool, StructureAnalysisError> {
112        let successors = analysis.get_successors(region_id)?;
113        let len = successors.len();
114
115        // Case 1: doWhile, if the region has an expression AND the successor is the same region.
116        for successor in &successors {
117            if successor.0 == region_id {
118                // Call the before_reduce hook
119                analysis.before_reduce(region_id);
120
121                if len == 1 {
122                    // TODO: Infinite loop: not implemented yet
123                    return Err(StructureAnalysisError::Other {
124                        message: "Infinite loop not implemented yet".to_string(),
125                        backtrace: Backtrace::capture(),
126                    });
127                }
128
129                let jump_expr = Self::extract_jump_expr(analysis, region_id)?;
130                let region_nodes = Self::get_region_nodes(analysis, region_id)?;
131                let cond: P<ControlFlowNode> = new_do_while(jump_expr, region_nodes).into();
132
133                Self::replace_region_nodes(analysis, region_id, cond)?;
134                return Ok(true);
135            }
136        }
137
138        // Case 2: while, if the region has an expression AND the successor's successor is the same region.
139        for successor in &successors {
140            if analysis.get_single_linear_successor(successor.0)? == Some(region_id)
141                && analysis.get_single_predecessor(successor.0)? == Some(region_id)
142            {
143                // Call the before_reduce hook
144                analysis.before_reduce(region_id);
145
146                // We have a while loop! Merge the regions.
147                let jump_expr = Self::extract_jump_expr(analysis, region_id)?;
148                let region_nodes = Self::get_region_nodes(analysis, successor.0)?;
149                let cond: P<ControlFlowNode> = new_cyclic_condition(
150                    jump_expr,
151                    region_nodes,
152                    analysis.get_branch_opcode(region_id)?,
153                )
154                .map_err(|e| StructureAnalysisError::AstNodeError {
155                    source: Box::new(e),
156                    backtrace: Backtrace::capture(),
157                })?
158                .into();
159
160                Self::merge_conditional(analysis, region_id, cond)?;
161                Self::cleanup_region(analysis, successor.0, region_id, region_id)?;
162                return Ok(true);
163            }
164        }
165        Ok(false)
166    }
167}
gbf_core/decompiler/structure_analysis/cyclic_region_reducer.rs

gbf_core/decompiler/structure_analysis/
cyclic_region_reducer.rs
